Hasan has P taka. He goes a chocolate shop. The chocolate shop has only 'Kitkat' and 'Dairy Milk'. The price of a single 'Dairy milk' is M taka and a single 'Kitkat' is N taka.

If any person wish to buy 'Dairy Milk', he/she must buy exactly 1 or 2 or 4 or 8 'Dairy Milks' at a time.

If any person wish to buy 'Kitkat', he/she must buy exactly 7 or 14 or 28 'Kitkats' at a time.

Hasan wants to spend as much money as he can. As, Hasan is weak in mathematics, he wants your help.

Now, you need to calculate the minimum remaining money that Hasan will have after buying chocolates.

Input

First line contains a positive integer T, which is the number of test cases.

In each test case there will be three integers P, M, N.

1 <= T <= 25

1 <= P <= 3*10^10

30 <= M, N <= 10^10

The summation of all P in all test case will not exceed 1.2*10^11

Output

For each test case print the minimum money that Hasan will have after buying chocolates in one line.

See the sample input outout for better understanding.

Example

Input:
3
150 30 35
167 40 35
99999989 31 31

Output:
0
7
3