M. Bridge IV
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Since they cannot find the third and fourth players, Diluc and Kaeya are playing a simplified version of contract bridge with only two players. A full deck of 52 cards is evenly split into two visible hands. Each player is randomly and independently marked as vulnerable or not.

Then, they start to bid the contract in turn, with Diluc bidding first. Players bid in turn, starting with Diluc. A bid is a contract consisting of a level (1–7) and a suit from the following hierarchy: C < D < H < S < N (No Trump). A bid can only be made if it outranks the current highest bid — that is, it has a higher level, or the same level with a higher suit. For example, if Diluc has bid 1H, Kaeya can bid 1S, 1N, or 2C, but he cannot bid 1C or 1H itself. Either player may pass. If both pass consecutively, bidding ends. The last bidder becomes the declarer, and the other becomes the defender.

The declarer must win at least $$$x+6$$$ tricks, where $$$x$$$ is the contract level. After all cards are played, the score is calculated. The declarer gains points if the contract is fulfilled; otherwise, the defender gains points. The total score is always zero-sum.

Let $$$x$$$ be the contract level, and $$$y$$$ be the number of extra tricks ($$$y \gt 0$$$ if over, $$$y \lt 0$$$ if under):

  • If the declarer fulfills the contract, his score consists of four parts:
    1. Trick Points:
      • $$$20x$$$ for suits C or D
      • $$$30x$$$ for suits H or S
      • $$$30x + 10$$$ for suit N
    2. Contract Bonus:
      • If Trick Points $$$\ge 100$$$: $$$+500$$$ if vulnerable, $$$+300$$$ otherwise
      • Otherwise: $$$+50$$$
    3. Overtrick Bonus (if $$$y \gt 0$$$):
      • $$$20y$$$ for suits C or D
      • $$$30y$$$ for suits H, S, or N
    4. Slam Bonus:
      • If $$$x = 7$$$: $$$+1500$$$ if vulnerable, $$$+1000$$$ otherwise
      • If $$$x = 6$$$: $$$+750$$$ if vulnerable, $$$+500$$$ otherwise
  • If the contract fails ($$$y \lt 0$$$), let $$$z = -y$$$ be the number of undertricks. The defender will gain score:
    • If the declarer is vulnerable:
      • $$$z = 1,2,3$$$: $$$200$$$, $$$500$$$, $$$800$$$
      • $$$z \ge 4$$$: $$$300z - 100$$$
    • If the declarer is not vulnerable:
      • $$$z = 1,2,3$$$: $$$100$$$, $$$300$$$, $$$500$$$
      • $$$z \ge 4$$$: $$$300z - 400$$$

For example, if Diluc is not vulnerable, declares 6N and wins $$$13$$$ tricks, he will win $$$(30\times6+10)+300+30+500=1020$$$ points. If Kaeya is vulnerable, declares 4S and wins $$$4$$$ tricks, he will lose $$$300\times(10-4)-100=1700$$$ points.

Specifically, if neither bids a contract during the bidding, neither of them gains score.

Both players are perfect analysts: they know exactly how many tricks they can win as declarer with each suit. Given this, bidding proceeds optimally for both sides to maximize their expected score. They are now tired of playing cards and want to know their score as long as the cards are assigned. Because double-dummy analysis is very complex, they will tell you the results and expect you to calculate the final score within 1 second.

Input

Each test contains multiple test cases. The first line contains one integer $$$t$$$ ($$$1\le t\le10^4$$$) — the number of test cases. The description of each test case follows.

The first line of each test case contains two integers $$$v_1,v_2$$$ $$$(0\le v_1,v_2\le1)$$$ — vulnerability of Diluc and Kaeya ($$$1$$$ means vulnerable).

The second line of each test case contains five integers $$$c_1,d_1,h_1,s_1,n_1$$$ $$$(0\le c_1,d_1,h_1,s_1,n_1\le13)$$$ — the number of tricks Diluc can win as declarer with each suit C, D, H, S, and N.

The third line of each test case contains five integers $$$c_2,d_2,h_2,s_2,n_2$$$ $$$(0\le c_2,d_2,h_2,s_2,n_2\le13)$$$ — the same numbers for Kaeya.

It is guaranteed that each test case corresponds to a valid double dummy analysis with a consistent deal.

Output

For each test case, output one integer — the final score Diluc gets, assuming both play optimally.

Example
Input
6
0 0
9 11 13 6 9
3 2 0 7 3
0 1
9 11 13 6 9
3 2 0 7 3
0 0
9 6 7 3 5
4 6 5 10 6
1 0
4 5 2 4 2
9 8 11 9 11
0 1
5 5 7 6 5
8 8 6 6 5
0 1
10 7 9 5 5
3 6 3 8 8
Output
1400
1510
-300
-460
-90
140
Note

In the first sample case, the optimal contract is 7S declared by Kaeya.

In the second sample case, the optimal contract is 7H declared by Diluc.