I often buy Coca-Cola from the vending machine at work. Usually, I buy several cokes at once, since my working mates also like coke. A coke in the vending machine costs 8 Rupees, and the machine accepts coins with the values 1, 5 and 10 Rupees only.
As soon as I press the coke button (After having inserted sufficient amount of money), I receive a coke followed by the exchange (i.e the excess amount, if any). The exchange is always given in as few coins as possible (this is uniquely determined by the coin set used). This procedure is repeated until I've bought all the cokes I want.
Note that I can pick up the coin exchange and use those coins when buying further cokes. The vending machine doesn't support buying more than one coke at the same time, if you want to buy more than one, you should pay for the first one, then get the exchange then insert money for the second one and so on.
Now, what is the least number of coins I must insert in total, given the number of cokes I want to buy and the number of coins I have of each value? You may assume that the machine won't run out of coins. If the given number of coins is insufficient to buy the quantity of cokes required, you can output "-1".
Input:
The first line in the input contains the number of test cases. Each case is then given on a line by itself. A test case consists of four integers: C (the number of cokes I want to buy), n1, n5, n10 (the number of coins of value 1, 5 and 10, respectively).
Output:
For each test case, output a line containing a single integer: the minimum number of coins needed to insert into the vending machine.
Constraints:
1<= T <=10
1 <= C <= 150
0 <= n1 <= 500
0 <= n5 <= 100
0 <= n10 <= 50