Game of Riddle

0

0 votes
Problem

"Bless us and splash us , precious . Thats a meaty mouthful . " said Gollum on seeing Bilbo Baggins . Poor Bilbo Baggins is lost in the Misty Mountains and worst of all now he is stuck with Gollum who wants to finish him off. As Mr. Bilbo Baggins is clever , he convinced Gollum to play a game of riddles where if Bilbo answers correctly to the riddle given by Gollum , he wins and Gollum shows him the way out of the mountains . But if he loses , then Golumn would finish him off. Gollum gives Bilbo a fixed quantity of sand , say x units and also gives the quantity of sand required for each digit (1-9) , i.e he gives 9 numbers (x1,x2...x9) where xi represents sand required for ith digit . Now he ask Baggins to output the largest number possible using the given x units of sand. Bilbo Baggins find this problem quite difficult and thus seeks your help .

Your task is simply to output the largest number possible which can be formed using x units of sand , given sand required for each digit. If its impossible to form a number, print '-1'.


Input

First line contains integer T , the number of test cases. T testcases follow. The first line of each testcase contains integer n. Following n lines contain 9 integers , the amount of sand required for each number.

Output

For each test case print largest number possible, if not possible to form the number , print -1 .

 

Constraints

  • 1 <= T <= 10
  • 1 <=n <= 10^6
  • 1 <=xi <= 10^5
Sample Input
3
5
9 4 2 2 6 3 2 2 1
2
5 11 2 2 5 8 9 10 19
5
9 9 9 9 9 9 9 9 9
Sample Output
99999
4
-1
Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

SAMPLE CASE 1 : Maximum sand available is 5 units . So maximum number that can be formed using 5 units of sand is 99999 where each digit '9' consumed 1 unit of sand.

SAMPLE CASE 3 : Maximum available sand is 5 units but sand required to form any of the 9 digits ( 1 to 9) is greater than maximum available sand which is 9 units . So its impossible to form any number and you have to print '-1' (without quotes).

NOTE : Ignore '0' digit . You have to form numbers without considering '0' digit.

Editor Image

?