Description

My World Cup is a fantastic board game. In this game, controlled by two players respectively, two different soccer teams meet each other in World Cup final. So, both sides are trying their best to win.

Alice and Bob are addicted to My World Cup recently. They always play together. Alice wants to figure out the probability of her winning. She turns to you for help.

First of all, you must be familiar with the special dice and cards for My World Cup.

The dice is six-sided. Two faces have a ball on them, while the other four faces do not. Dice is an important accessory for My World Cup.

There are many cards in My World Cup. Each card belongs to one of four types: foul, offense, defense, and attack. As well, each card has speed and power.

When two cards from different sides meet, both of them may take some effect, which depends on both cards' type:

1. If your card is an offense: If the other card is a foul, your card has no effect. Otherwise, your team can have a shoot of your card’s power. A shoot of power k means that you can throw the dice for k times (or do nothing while k is less or equal to zero) . If a ball on the dice is face up for one or more times, your team will score one goal; otherwise, you get nothing. But please note that if the other card is a defense, then before your shoot, your card's power will be reduced by the defense card's power.

2. If your card is a defense: If the other card is an attack, you will make a rapid counter-attack. In the rapid counter-attack, your team will have a shoot of your card’s power minus the attack card’s power.

3. If your card is an attack: Assume that your card’s power is P1 and the other card’s power is P2. If the other card is a foul, your card will have no effect. If the other card is a defense, your team will score max{ P1-P2,0} goals. Otherwise your team will score max{ P1, 0} goals.

4. If your card is a foul: You must throw a dice. If a ball on the dice is face up, your opponent will gain a penalty kick(A penalty kick is regarded as a shoot of power 3); otherwise, your card has no effect.

The game's process in detail is going to be explained below.

1. Preparation: (1) One player is decided to be home and the other is away. (2) Each player has five cards, four are on the field, one is off the field.

2. During each turn: (1) Each player selects one card with the largest speed value on his own field. If two or more cards meet the conditions, he can choose anyone among them. (2) Choose the one with larger speed value among two cards selected from step (1) to be the main card. If two cards have the same speed, the one comes from the home team will be chosen. (3) The owner of the main card can choose one card as the subordinate card among the cards in the opponent's field( including the card selected from step(1) by the opponent). (4) The main card and the subordinate card meet each other and both take their effects. (5) Both the main card and the subordinate card are removed from the field.

3. After four turns, there is no card on the field. At this time, if a team scores more goals than the other, the victory are theirs. However, if both teams score an equal number of goals, an extra time will be added - each player should put his last card on the field, and the game continues for one more turn.

4. If the game ends as a draw even after the extra time, well, an exciting penalty shoot-out is used to determine the winner: (1) Teams take turns to take penalty kicks, until each has taken five kicks. However, if one side has scored more goals than the other could possibly reach with all of its remaining penalty kicks, the shoot-out ends immediately. (2) If the teams still have scored an equal number of goals at the end of these five rounds of penalty kicks, sudden death rounds of one penalty kick each are used, until one side scores and the other does not. (3) The team scores more goals at last is the winner.

Now, give you the full information of Alice's and Bob's cards, can you calculate the probability of Alice's win while both of them are taking optimal strategy to win the game. Note that Alice is always home.

Input

The input begins with a line containing an integer T (1 <= T <= 30), the number of test cases.

Each test case contains 10 lines. Each line contains three integers t, s and p (0 <= t <= 3, 1 <= s <= 10, 0 <= p <= 9) indicating a single card's information - t is the type (0 for foul, 1 for offense, 2 for defense, and 3 for attack), s is the speed, and p is the power of the card. The first five cards belong to Alice (first four are on the field and the fifth is off the field), and the last five cards belong to Bob (also first four are on the field and the fifth is off the field initially).

Output

For each test case, you just need to print the probability of Alice's wining as a percentage in one line (rounded to the nearest integer).

2
1 6 4
3 6 1
2 7 3
3 5 1
0 9 0
2 5 5
3 3 2
2 6 4
3 3 2
2 5 5
3 6 1
3 6 1
3 6 1
3 6 1
3 6 2
3 6 1
3 1 3
3 6 1
3 6 1
3 6 1

4
0

Source

Fuzhou 2011