KOPC12D - K12-Generating Big Numbers II

no tags 

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 3. 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

hide comments
vinay1998: 2019-01-15 13:12:42

Beware : Answer to the testcase 0 0 0 0 0 0 0 0 is 1.

DEEPAK619: 2015-07-31 17:06:19

Just brute force!!!!!!!

__hk__: 2015-05-30 13:01:27

Nice implementation....

NEXES: 2014-12-14 10:42:38

Good one....................

Bhavik: 2014-02-11 17:33:29

easy.. :)

Sameer: 2014-02-09 12:29:55

I just laughed after solving this :)

Xunie J: 2012-03-14 11:39:59

why the answer to this test 0 0 0 0 0 0 0 0 is 1??


Added by:Radhakrishnan Venkataramani
Date:2012-01-31
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64