Internet Problem Solving Contest

• Easy input data set – T1
• Hard input data set – T2

You are standing in a town with infinitely many houses. Currently, the houses do not have any house numbers. You were given the task to fix this.

You have a box with plastic digits. For each i between 0 and 9, inclusive, there are d_i copies of the digit i in your box. You can number a house by sticking the appropriate digits to its wall. For example, on the house number 474 you will use two digits 4 and one digit 7.

You have decided that you will number the houses sequentially, starting from 1. How many houses can you number before you run out of digits?

Problem specification

You are given the counts d₀, …, d₉ of the digits in your box. Find the largest x such that you are able to write the numbers 1 through x using your set of digits.

Input specification

The first line of the input file contains an integer t specifying the number of test cases. Each test case is preceded by a blank line. Each test case consists of a single line containing 10 nonnegative integers – the counts of digits 0 through 9.

In the easy subproblem T1 the sum of all d_i will be at most 10⁷.

In the hard subproblem T2 the sum of all d_i will be at most 10¹⁶.

Output specification

For each test case, output a single line with the answer to the test case.

Example

Input:

1

1 3 1 1 2 1 1 2 1 1

Output:

10

With the digits you have, you are able to build the numbers 1 through 10. Once you do so, you will be left with three digits: one 1, one 4, and one 7. This is not enough to construct the number 11.