시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB0000.000%

## 문제

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 di 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?

You are given the counts d0, …, d9 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.

## 출력

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

## 서브태스크

번호배점제한
Easy1

The sum of all di will be at most 107.

Hard2

The sum of all di will be at most 1016.

## 예제 입력 1

1

1 3 1 1 2 1 1 2 1 1


## 예제 출력 1

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.

## 채점 및 기타 정보

• 예제는 채점하지 않는다.