Problem: You are given three integers a, b and c.

Find two positive integers x and y (x > 0, y > 0) such that: 

  * the decimal representation of x without leading zeroes consists of a digits; 
  * the decimal representation of y without leading zeroes consists of b digits; 
  * the decimal representation of gcd(x, y) without leading zeroes consists of c digits. 



gcd(x, y) denotes the [greatest common divisor (GCD)](https://en.wikipedia.org/wiki/Greatest_common_divisor) of integers x and y.

Output x and y. If there are multiple answers, output any of them.

Input

The first line contains a single integer t (1 ≤ t ≤ 285) — the number of testcases.

Each of the next t lines contains three integers a, b and c (1 ≤ a, b ≤ 9, 1 ≤ c ≤ min(a, b)) — the required lengths of the numbers.

It can be shown that the answer exists for all testcases under the given constraints.

Additional constraint on the input: all testcases are different.

Output

For each testcase print two positive integers — x and y (x > 0, y > 0) such that 

  * the decimal representation of x without leading zeroes consists of a digits; 
  * the decimal representation of y without leading zeroes consists of b digits; 
  * the decimal representation of gcd(x, y) without leading zeroes consists of c digits. 

Example

Input


4
2 3 1
2 2 2
6 6 2
1 1 1


Output


11 492
13 26
140133 160776
1 1

Note

In the example: 

  1. gcd(11, 492) = 1 
  2. gcd(13, 26) = 13 
  3. gcd(140133, 160776) = 21 
  4. gcd(1, 1) = 1 

Solution (in PYTHON3):

Solution:
ans = [[[0] * 10 for i in range(10)] for j in range(10)]
ans[1][1][1] = (1,1)
ans[1][2][1] = (1,10)
ans[1][3][1] = (1,100)
ans[1][4][1] = (1,1000)
ans[1][5][1] = (1,10000)
ans[1][6][1] = (1,100000)
ans[1][7][1] = (1,1000000)
ans[1][8][1] = (1,10000000)
ans[1][9][1] = (1,100000000)
ans[2][1][1] = (10,1)
ans[2][2][1] = (10,11)
ans[2][2][2] = (10,10)
ans[2][3][1] = (10,111)
ans[2][3][2] = (10,100)
ans[2][4][1] = (10,1111)
ans[2][4][2] = (10,1000)
ans[2][5][1] = (10,11111)
ans[2][5][2] = (10,10000)
ans[2][6][1] = (10,111111)
ans[2][6][2] = (10,100000)
ans[2][7][1] = (10,1111111)
ans[2][7][2] = (10,1000000)
ans[2][8][1] = (10,11111111)
ans[2][8][2] = (10,10000000)
ans[2][9][1] = (10,111111111)
ans[2][9][2] = (10,100000000)
ans[3][1][1] = (100,1)
ans[3][2][1] = (100,11)
ans[3][2][2] = (100,10)
ans[3][3][1] = (100,111)
ans[3][3][2] = (100,110)
ans[3][3][3] = (100,100)
ans[3][4][1] = (100,1111)
ans[3][4][2] = (100,1110)
ans[3][4][3] = (100,1000)
ans[3][5][1] = (100,11111)
ans[3][5][2] = (100,11110)
ans[3][5][3] = (100,10000)
ans[3][6][1] = (100,111111)
ans[3][6][2] = (100,111110)
ans[3][6][3] = (100,100000)
ans[3][7][1] = (100,1111111)
ans[3][7][2] = (100,1111110)
ans[3][7][3] = (100,1000000)
ans[3][8][1] = (100,11111111)
ans[3][8][2] = (100,11111110)
ans[3][8][3] = (100,10000000)
ans[3][9][1] = (100,111111111)
ans[3][9][2] = (100,111111110)
ans[3][9][3] = (100,100000000)
ans[4][1][1] = (1000,1)
ans[4][2][1] = (1000,11)
ans[4][2][2] = (1000,10)
ans[4][3][1] = (1000,111)
ans[4][3][2] = (1000,110)
ans[4][3][3] = (1000,100)
ans[4][4][1] = (1000,1111)
ans[4][4][2] = (1000,1110)
ans[4][4][3] = (1000,1100)
ans[4][4][4] = (1000,1000)
ans[4][5][1] = (1000,11111)
ans[4][5][2] = (1000,11110)
ans[4][5][3] = (1000,11100)
ans[4][5][4] = (1000,10000)
ans[4][6][1] = (1000,111111)
ans[4][6][2] = (1000,111110)
ans[4][6][3] = (1000,111100)
ans[4][6][4] = (1000,100000)
ans[4][7][1] = (1000,1111111)
ans[4][7][2] = (1000,1111110)
ans[4][7][3] = (1000,1111100)
ans[4][7][4] = (1000,1000000)
ans[4][8][1] = (1000,11111111)
ans[4][8][2] = (1000,11111110)
ans[4][8][3] = (1000,11111100)
ans[4][8][4] = (1000,10000000)
ans[4][9][1] = (1000,111111111)
ans[4][9][2] = (1000,111111110)
ans[4][9][3] = (1000,111111100)
ans[4][9][4] = (1000,100000000)
ans[5][1][1] = (10000,1)
ans[5][2][1] = (10000,11)
ans[5][2][2] = (10000,10)
ans[5][3][1] = (10000,111)
ans[5][3][2] = (10000,110)
ans[5][3][3] = (10000,100)
ans[5][4][1] = (10000,1111)
ans[5][4][2] = (10000,1110)
ans[5][4][3] = (10000,1100)
ans[5][4][4] = (10000,1000)
ans[5][5][1] = (10000,11111)
ans[5][5][2] = (10000,11110)
ans[5][5][3] = (10000,11100)
ans[5][5][4] = (10000,11000)
ans[5][5][5] = (10000,10000)
ans[5][6][1] = (10000,111111)
ans[5][6][2] = (10000,111110)
ans[5][6][3] = (10000,111100)
ans[5][6][4] = (10000,111000)
ans[5][6][5] = (10000,100000)
ans[5][7][1] = (10000,1111111)
ans[5][7][2] = (10000,1111110)
ans[5][7][3] = (10000,1111100)
ans[5][7][4] = (10000,1111000)
ans[5][7][5] = (10000,1000000)
ans[5][8][1] = (10000,11111111)
ans[5][8][2] = (10000,11111110)
ans[5][8][3] = (10000,11111100)
ans[5][8][4] = (10000,11111000)
ans[5][8][5] = (10000,10000000)
ans[5][9][1] = (10000,111111111)
ans[5][9][2] = (10000,111111110)
ans[5][9][3] = (10000,111111100)
ans[5][9][4] = (10000,111111000)
ans[5][9][5] = (10000,100000000)
ans[6][1][1] = (100000,1)
ans[6][2][1] = (100000,11)
ans[6][2][2] = (100000,10)
ans[6][3][1] = (100000,111)
ans[6][3][2] = (100000,110)
ans[6][3][3] = (100000,100)
ans[6][4][1] = (100000,1111)
ans[6][4][2] = (100000,1110)
ans[6][4][3] = (100000,1100)
ans[6][4][4] = (100000,1000)
ans[6][5][1] = (100000,11111)
ans[6][5][2] = (100000,11110)
ans[6][5][3] = (100000,11100)
ans[6][5][4] = (100000,11000)
ans[6][5][5] = (100000,10000)
ans[6][6][1] = (100000,111111)
ans[6][6][2] = (100000,111110)
ans[6][6][3] = (100000,111100)
ans[6][6][4] = (100000,111000)
ans[6][6][5] = (100000,110000)
ans[6][6][6] = (100000,100000)
ans[6][7][1] = (100000,1111111)
ans[6][7][2] = (100000,1111110)
ans[6][7][3] = (100000,1111100)
ans[6][7][4] = (100000,1111000)
ans[6][7][5] = (100000,1110000)
ans[6][7][6] = (100000,1000000)
ans[6][8][1] = (100000,11111111)
ans[6][8][2] = (100000,11111110)
ans[6][8][3] = (100000,11111100)
ans[6][8][4] = (100000,11111000)
ans[6][8][5] = (100000,11110000)
ans[6][8][6] = (100000,10000000)
ans[6][9][1] = (100000,111111111)
ans[6][9][2] = (100000,111111110)
ans[6][9][3] = (100000,111111100)
ans[6][9][4] = (100000,111111000)
ans[6][9][5] = (100000,111110000)
ans[6][9][6] = (100000,100000000)
ans[7][1][1] = (1000000,1)
ans[7][2][1] = (1000000,11)
ans[7][2][2] = (1000000,10)
ans[7][3][1] = (1000000,111)
ans[7][3][2] = (1000000,110)
ans[7][3][3] = (1000000,100)
ans[7][4][1] = (1000000,1111)
ans[7][4][2] = (1000000,1110)
ans[7][4][3] = (1000000,1100)
ans[7][4][4] = (1000000,1000)
ans[7][5][1] = (1000000,11111)
ans[7][5][2] = (1000000,11110)
ans[7][5][3] = (1000000,11100)
ans[7][5][4] = (1000000,11000)
ans[7][5][5] = (1000000,10000)
ans[7][6][1] = (1000000,111111)
ans[7][6][2] = (1000000,111110)
ans[7][6][3] = (1000000,111100)
ans[7][6][4] = (1000000,111000)
ans[7][6][5] = (1000000,110000)
ans[7][6][6] = (1000000,100000)
ans[7][7][1] = (1000000,1111111)
ans[7][7][2] = (1000000,1111110)
ans[7][7][3] = (1000000,1111100)
ans[7][7][4] = (1000000,1111000)
ans[7][7][5] = (1000000,1110000)
ans[7][7][6] = (1000000,1100000)
ans[7][7][7] = (1000000,1000000)
ans[7][8][1] = (1000000,11111111)
ans[7][8][2] = (1000000,11111110)
ans[7][8][3] = (1000000,11111100)
ans[7][8][4] = (1000000,11111000)
ans[7][8][5] = (1000000,11110000)
ans[7][8][6] = (1000000,11100000)
ans[7][8][7] = (1000000,10000000)
ans[7][9][1] = (1000000,111111111)
ans[7][9][2] = (1000000,111111110)
ans[7][9][3] = (1000000,111111100)
ans[7][9][4] = (1000000,111111000)
ans[7][9][5] = (1000000,111110000)
ans[7][9][6] = (1000000,111100000)
ans[7][9][7] = (1000000,100000000)
ans[8][1][1] = (10000000,1)
ans[8][2][1] = (10000000,11)
ans[8][2][2] = (10000000,10)
ans[8][3][1] = (10000000,111)
ans[8][3][2] = (10000000,110)
ans[8][3][3] = (10000000,100)
ans[8][4][1] = (10000000,1111)
ans[8][4][2] = (10000000,1110)
ans[8][4][3] = (10000000,1100)
ans[8][4][4] = (10000000,1000)
ans[8][5][1] = (10000000,11111)
ans[8][5][2] = (10000000,11110)
ans[8][5][3] = (10000000,11100)
ans[8][5][4] = (10000000,11000)
ans[8][5][5] = (10000000,10000)
ans[8][6][1] = (10000000,111111)
ans[8][6][2] = (10000000,111110)
ans[8][6][3] = (10000000,111100)
ans[8][6][4] = (10000000,111000)
ans[8][6][5] = (10000000,110000)
ans[8][6][6] = (10000000,100000)
ans[8][7][1] = (10000000,1111111)
ans[8][7][2] = (10000000,1111110)
ans[8][7][3] = (10000000,1111100)
ans[8][7][4] = (10000000,1111000)
ans[8][7][5] = (10000000,1110000)
ans[8][7][6] = (10000000,1100000)
ans[8][7][7] = (10000000,1000000)
ans[8][8][1] = (10000000,11111111)
ans[8][8][2] = (10000000,11111110)
ans[8][8][3] = (10000000,11111100)
ans[8][8][4] = (10000000,11111000)
ans[8][8][5] = (10000000,11110000)
ans[8][8][6] = (10000000,11100000)
ans[8][8][7] = (10000000,11000000)
ans[8][8][8] = (10000000,10000000)
ans[8][9][1] = (10000000,111111111)
ans[8][9][2] = (10000000,111111110)
ans[8][9][3] = (10000000,111111100)
ans[8][9][4] = (10000000,111111000)
ans[8][9][5] = (10000000,111110000)
ans[8][9][6] = (10000000,111100000)
ans[8][9][7] = (10000000,111000000)
ans[8][9][8] = (10000000,100000000)
ans[9][1][1] = (100000000,1)
ans[9][2][1] = (100000000,11)
ans[9][2][2] = (100000000,10)
ans[9][3][1] = (100000000,111)
ans[9][3][2] = (100000000,110)
ans[9][3][3] = (100000000,100)
ans[9][4][1] = (100000000,1111)
ans[9][4][2] = (100000000,1110)
ans[9][4][3] = (100000000,1100)
ans[9][4][4] = (100000000,1000)
ans[9][5][1] = (100000000,11111)
ans[9][5][2] = (100000000,11110)
ans[9][5][3] = (100000000,11100)
ans[9][5][4] = (100000000,11000)
ans[9][5][5] = (100000000,10000)
ans[9][6][1] = (100000000,111111)
ans[9][6][2] = (100000000,111110)
ans[9][6][3] = (100000000,111100)
ans[9][6][4] = (100000000,111000)
ans[9][6][5] = (100000000,110000)
ans[9][6][6] = (100000000,100000)
ans[9][7][1] = (100000000,1111111)
ans[9][7][2] = (100000000,1111110)
ans[9][7][3] = (100000000,1111100)
ans[9][7][4] = (100000000,1111000)
ans[9][7][5] = (100000000,1110000)
ans[9][7][6] = (100000000,1100000)
ans[9][7][7] = (100000000,1000000)
ans[9][8][1] = (100000000,11111111)
ans[9][8][2] = (100000000,11111110)
ans[9][8][3] = (100000000,11111100)
ans[9][8][4] = (100000000,11111000)
ans[9][8][5] = (100000000,11110000)
ans[9][8][6] = (100000000,11100000)
ans[9][8][7] = (100000000,11000000)
ans[9][8][8] = (100000000,10000000)
ans[9][9][1] = (100000000,111111111)
ans[9][9][2] = (100000000,111111110)
ans[9][9][3] = (100000000,111111100)
ans[9][9][4] = (100000000,111111000)
ans[9][9][5] = (100000000,111110000)
ans[9][9][6] = (100000000,111100000)
ans[9][9][7] = (100000000,111000000)
ans[9][9][8] = (100000000,110000000)
ans[9][9][9] = (100000000,100000000)

for tt in range(int(input())):
    a,b,c = map(int,input().split())
    print(*ans[a][b][c])