Hasan has P taka. He goes to 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¹⁰

30 ≤ M, N ≤ 10¹⁰

The summation of all P in all test case will not exceed 1.2×10¹¹

Output

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

See the sample input output for better understanding.

Example

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

Output:
0
7
3