链接：https://codeforces.com/problemset/problem/1250/H

You have a set of birthday cake candles. Each of such candles represents a digit between 00 and 99, inclusive.

Example of birthday cake candles.

Let's denote the candle representing the digit dd as dd-candle.

Your set contains c0c0 instances of 00-candles, c1c1 instances of 11-candles and so on. So, the total number of candles is c0+c1+⋯+c9c0+c1+⋯+c9.

These digits are needed to wish your cat a happy birthday. For each birthday, starting with the first, you want to compose the age of the cat using the digits from the set.

Since you light candles for a very short time, candles don't have time to burn out. For this reason you can reuse candles an arbitrary number of times (therefore your set of candles never changes).

For example, if you have one instance of each digit (i.e. c0=c1=⋯=c9=1c0=c1=⋯=c9=1), you can compose any number from 11 to 1010 using this set, but you cannot compose 1111.

You have to determine the first birthday, on which you cannot compose the age of the cat using the candles from your set. In other words, find the minimum number yy such that all numbers from 11 to y−1y−1 can be composed by digits from your set, but yy cannot be composed.

Input

The first line contains an integer tt (1≤t≤1041≤t≤104) — the number of test cases in the input.

The only line of each test case contains ten integer numbers c0,c1,…,c9c0,c1,…,c9 (0≤ci≤1050≤ci≤105) — the number of 00-candles, 11-candles, 22-candles and so on.

It is guaranteed that the sum of all cici in the input does not exceed 106106.

Output

For each test case, output one integer in single line — the minimum age which cannot be composed by candles from your set. Please note that the age can be quite large (it may exceed the standard 64-bit integer types in your programming language).

Example

input

Copy

4
1 1 1 1 1 1 1 1 1 1
0 0 1 1 2 2 3 3 4 4
1 2 1 2 1 3 1 0 0 0
0 1 2 1 4 3 1 1 2 1

output

Copy

11
1
7
10
#include<bits/stdc++.h>
using namespace std;
long long t,n,k;
long long a[11];
int main()
{
	cin>>t;
	while(t--)
	{
		int min1=1e5+10;
		k=-1;
		for(int i=0;i<=9;i++)
		{
			cin>>a[i];
		}
		a[10]=a[0];
		for(int i=1;i<=10;i++)
		{
			if(a[i]<min1)
			{
				min1=a[i];
				k=i;
			}
		}
		if(k!=10)
		{
			for(int i=1;i<=a[k]+1;i++)
			cout<<k;
		}
		else
		{
			cout<<1;
			for(int i=1;i<=a[k]+1;i++)
			cout<<0;
		}
		cout<<endl;
		
	}
}