Problem I. Item Enhancement II ≡

Statement

Petya likes to play MMORPG and wants to beat everyone in PvP.

He just bought and enhanced an awesome weapon, but he didn't have enough money for armor.

Fortunately, the server he plays on supports the transfer of enhancement levels, and Petya knows how to make money from it.

He buys cheap items, and if they get a high enhancement level, he can sell them for a high price

To determine if this is a profitable strategy, certain calculations need to be made.

However, Petya is not the best programmer/mathematician, so he asks for your help.

The starting enhancement level of an item is 0.

The maximum possible level is 12.

To increase the enhancement level by 1 with a certain probability, 1 Immortal Stone is required.

In case of failure, the enhancement level of the item resets to zero (exceptions are specified below).

Additionally, along with the Immortal Stone, one special stone can be used.

The server offers the following special stones:

Sky Stone - significantly increases the chances of success.

Underground Stone - slightly increases the chances of success, in case of failure it decreases the enhancement level by 1.

Stone of Creation - has low chances of success, but in case of failure it does not reduce the enhancement level.

I-th level Dragon Orb - guarantees successful enhancement up to level I and lower, no effect for other levels.

Petya knows the prices of all the required resources and the chances of successful enhancement.

You should calculate the minimum average cost for each level so that Petya can assess which level is most profitable to trade.

Input format

The first line contains an integer T - the number of input data sets.

Next follows the description of each set.

The first line contains four integers: A, B, C, D:

A: price of an Immortal Stone.

B: price of a Sky Stone.

C: price of an Underground Stone.

D: price of a Stone of Creation.

The next 12 lines contain the following numbers: W_i, X_i, Y_i, Z_i, E_i:

W_i: chance of success for level i with Immortal Stone.

X_i: chance of success for level i with Immortal Stone + Sky Stone.

Y_i: chance of success for level i with Immortal Stone + Underground Stone.

Z_i: chance of success for level i with Immortal Stone + Stone of Creation.

E_i: an integer, the price of i-th level Dragon Orb.

Output format

For each input data set, output 12 lines.

In the i-th line a single integer (rounded down) - the minimum average cost of i-th level enhancement.

Constraints

1 ≤ T ≤ 500

1 ≤ A, B, C, D, E_i ≤ 10⁹

0.05 ≤ W_i, X_i, Y_i ≤ 0.95

0.0001 ≤ Z_i ≤ 0.95

Z_i ≤ W_i ≤ Y_i ≤ X_i

Sample tests

3
40000 200000 199000 198000
0.50 0.60 0.535 0.4000 200000
0.30 0.45 0.335 0.2500 250000
0.30 0.45 0.335 0.1000 2000000
0.30 0.45 0.335 0.0400 5000000
0.30 0.45 0.335 0.0167 12000000
0.30 0.45 0.335 0.0077 26000000
0.30 0.45 0.335 0.0047 42500000
0.30 0.45 0.335 0.0025 80000000
0.25 0.40 0.285 0.0013 153000000
0.20 0.35 0.235 0.0010 286000000
0.12 0.27 0.155 0.0004 500000000
0.05 0.20 0.085 0.0002 1000000000
55000 187000 186000 185000
0.50 0.60 0.535 0.0001 1000000000
0.30 0.45 0.335 0.0001 1000000000
0.30 0.45 0.335 0.0001 1000000000
0.30 0.45 0.335 0.0001 1000000000
0.30 0.45 0.335 0.0001 1000000000
0.30 0.45 0.335 0.0001 1000000000
0.30 0.45 0.335 0.0001 1000000000
0.30 0.45 0.335 0.0001 1000000000
0.25 0.40 0.285 0.0001 1000000000
0.20 0.35 0.235 0.1900 1000000000
0.10 0.10 0.100 0.0001 1000000000
0.05 0.20 0.190 0.0001 1000000000
1 1000000000 1000000000 1000000000
0.05 0.05 0.05 0.0001 1000000000
0.05 0.05 0.05 0.0001 1000000000
0.05 0.05 0.05 0.0001 1000000000
0.05 0.05 0.05 0.0001 1000000000
0.05 0.05 0.05 0.0001 1000000000
0.05 0.05 0.05 0.0001 1000000000
0.05 0.05 0.05 0.0001 1000000000
0.05 0.05 0.05 0.0001 1000000000
0.05 0.05 0.05 0.0001 1000000000
0.05 0.05 0.05 0.0001 1000000000
0.05 0.05 0.05 0.0001 1000000000
0.05 0.05 0.05 0.0001 1

80000
370000
1355555
3545679
8412620
18787293
40095228
83106502
191850575
429850575
929890575
1929930575
110000
550000
1760000
4448888
10424197
23005034
48698336
100420862
231026496
232289654
246068075
306076081
2
4
6
8
10
12
14
16
18
20
22
24