Welcome to ZOJ
Information
Problems
Runs
Statistics
Ranklist
Clarification
93 - ZOJ Monthly, July 2010 - E
Football Gambling II

Time Limit: 3 Seconds      Memory Limit: 65536 KB

The 2010 FIFA World Cup toke place between 11 June and 11 July 2010 in South Africa. Being a non-fans, asmn likes football gambling more than the football match itself. Of course, he won't use real money, he just gamble on the renren.com for fun using the virtual gold coin.

The rule of football gambling is simple. The bookmaker display three decimal numbers a, b, c before the match between team X and team Y. Number a is the odds for team X will win the game. Number b is the odds for they will get a draw. Number c is the odds for team X will lose the game.

Odds means that if you bet x gold coins, you will get floor(odds * x) gold coins in total if you guess the right result, or you will get nothing.

The Odds of the online gambling is higher than that in the real gambling because the gold coins are virtual. After several gambling, asmn found that, sometimes the odds are too high that it is possible to find a way to bet on three result at the same time, so that he can win money whatever the result is.

After several gambling, asmn lose a lot of money. So he decide not to take any risk in the following gambling. Now, given that asmn has s gold coins before each match and the odds for this math, you should caluate the maximum number of coins asmn will have after the gambling in the worst situation.

Input

The input consists of N cases. The first line of the input contains a positive integer N(N <= 100). Each case contains an integer and three decimal numbers s, a, b and c (0 < coins < 1000000, 1 < a, b,c < 100), the meaning of which is described above. Each decimal number will have exactly two digits after the decimal point.

Output

For each case, output the maximum number of coins that asmn will have after the match in the worst situation.

Sample Input

4
3 3.30 3.30 3.30
30 3.30 3.30 3.30
1 30.00 50.00 20.00
42 2.00 3.00 7.00

Sample Output

3
33
1
43

Hint

In the third case, the odds are very high, but asmn has only one coin. If he join the gambling, he may lost his last coin.


Author: WANG, Yelei
Source: ZOJ Monthly, July 2010
Submit    Status