You are given the count of each digits and you have to create a number with these available digits.Let the number be X. In X each digit should not occupy any position which is divisible by the digit. 2 shouldn't occupy 2,4,6,8.. th positions and 7 shouldn't occupy 7,14th positions. Position of unit's place is 1, hundreds' place is 2. Suppose X =abcdef, f is in position 1 ,e is in position 2,d is in position 3, a is in position 6.

Now Find the length of smallest X  possible while filling the remaining postions with zeros.Minimize the length of the number generated.

Example: Count of 2=2,Count of 4 =2.

X can  be  40242, 20442. But we need only the length of the number which is 5.

Input

The first line of input file contains T which denotes the number of test cases.This is followed by T lines where each of these T lines contains 8 space seperated integers which denotes the count of 2's , count of 3's,count of 4's .. upto count of 9's.

Note: Count of 1's will not be given as 1 divides every position of the number and Zeros can be placed in any position.

T<=50,count of each digit<=20.

Output

The output should contain T lines each line with the answer  corresponding to a test case.

Example

Input:
2
2 0 2 0 0 0 0 0 
20 20 20 20 20 20 20 20
Output:
5
160