## IPSC 2015

## Problem T – Town

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*_{0}, …, *d*_{9} 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.

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^{7}.

In the **hard subproblem T2** the sum of all *d*_{i} will be at most 10^{16}.

### 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.*