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 2nd, 4th, 6th, 8th ... positions and 7 shouldn't occupy 7th, 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 positions with zeros. Minimize the length of the number generated.

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

X can be 40242 or 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 separated integers which denotes the count of 2's, count of 3's, count of 4's ... up to 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