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:
t = int(input())
for _ in range(t):
    a,b,c = map(int,input().split())
    if a == 1 and b == 1 and c == 1:
        print(1, 1)
    if a == 1 and b == 2 and c == 1:
        print(1, 10)
    if a == 1 and b == 3 and c == 1:
        print(1, 100)
    if a == 1 and b == 4 and c == 1:
        print(1, 1000)
    if a == 1 and b == 5 and c == 1:
        print(1, 10000)
    if a == 1 and b == 6 and c == 1:
        print(1, 100000)
    if a == 1 and b == 7 and c == 1:
        print(1, 1000000)
    if a == 1 and b == 8 and c == 1:
        print(1, 10000000)
    if a == 1 and b == 9 and c == 1:
        print(1, 100000000)
    if a == 2 and b == 1 and c == 1:
        print(10, 1)
    if a == 2 and b == 2 and c == 1:
        print(10, 11)
    if a == 2 and b == 2 and c == 2:
        print(10, 10)
    if a == 2 and b == 3 and c == 1:
        print(10, 101)
    if a == 2 and b == 3 and c == 2:
        print(10, 100)
    if a == 2 and b == 4 and c == 1:
        print(10, 1001)
    if a == 2 and b == 4 and c == 2:
        print(10, 1000)
    if a == 2 and b == 5 and c == 1:
        print(10, 10001)
    if a == 2 and b == 5 and c == 2:
        print(10, 10000)
    if a == 2 and b == 6 and c == 1:
        print(10, 100001)
    if a == 2 and b == 6 and c == 2:
        print(10, 100000)
    if a == 2 and b == 7 and c == 1:
        print(10, 1000001)
    if a == 2 and b == 7 and c == 2:
        print(10, 1000000)
    if a == 2 and b == 8 and c == 1:
        print(10, 10000001)
    if a == 2 and b == 8 and c == 2:
        print(10, 10000000)
    if a == 2 and b == 9 and c == 1:
        print(10, 100000001)
    if a == 2 and b == 9 and c == 2:
        print(10, 100000000)
    if a == 3 and b == 1 and c == 1:
        print(100, 1)
    if a == 3 and b == 2 and c == 1:
        print(100, 11)
    if a == 3 and b == 2 and c == 2:
        print(100, 10)
    if a == 3 and b == 3 and c == 1:
        print(100, 101)
    if a == 3 and b == 3 and c == 2:
        print(100, 110)
    if a == 3 and b == 3 and c == 3:
        print(100, 100)
    if a == 3 and b == 4 and c == 1:
        print(100, 1001)
    if a == 3 and b == 4 and c == 2:
        print(100, 1010)
    if a == 3 and b == 4 and c == 3:
        print(100, 1000)
    if a == 3 and b == 5 and c == 1:
        print(100, 10001)
    if a == 3 and b == 5 and c == 2:
        print(100, 10010)
    if a == 3 and b == 5 and c == 3:
        print(100, 10000)
    if a == 3 and b == 6 and c == 1:
        print(100, 100001)
    if a == 3 and b == 6 and c == 2:
        print(100, 100010)
    if a == 3 and b == 6 and c == 3:
        print(100, 100000)
    if a == 3 and b == 7 and c == 1:
        print(100, 1000001)
    if a == 3 and b == 7 and c == 2:
        print(100, 1000010)
    if a == 3 and b == 7 and c == 3:
        print(100, 1000000)
    if a == 3 and b == 8 and c == 1:
        print(100, 10000001)
    if a == 3 and b == 8 and c == 2:
        print(100, 10000010)
    if a == 3 and b == 8 and c == 3:
        print(100, 10000000)
    if a == 3 and b == 9 and c == 1:
        print(100, 100000001)
    if a == 3 and b == 9 and c == 2:
        print(100, 100000010)
    if a == 3 and b == 9 and c == 3:
        print(100, 100000000)
    if a == 4 and b == 1 and c == 1:
        print(1000, 1)
    if a == 4 and b == 2 and c == 1:
        print(1000, 11)
    if a == 4 and b == 2 and c == 2:
        print(1000, 10)
    if a == 4 and b == 3 and c == 1:
        print(1000, 101)
    if a == 4 and b == 3 and c == 2:
        print(1000, 110)
    if a == 4 and b == 3 and c == 3:
        print(1000, 100)
    if a == 4 and b == 4 and c == 1:
        print(1000, 1001)
    if a == 4 and b == 4 and c == 2:
        print(1000, 1010)
    if a == 4 and b == 4 and c == 3:
        print(1000, 1100)
    if a == 4 and b == 4 and c == 4:
        print(1000, 1000)
    if a == 4 and b == 5 and c == 1:
        print(1000, 10001)
    if a == 4 and b == 5 and c == 2:
        print(1000, 10010)
    if a == 4 and b == 5 and c == 3:
        print(1000, 10100)
    if a == 4 and b == 5 and c == 4:
        print(1000, 10000)
    if a == 4 and b == 6 and c == 1:
        print(1000, 100001)
    if a == 4 and b == 6 and c == 2:
        print(1000, 100010)
    if a == 4 and b == 6 and c == 3:
        print(1000, 100100)
    if a == 4 and b == 6 and c == 4:
        print(1000, 100000)
    if a == 4 and b == 7 and c == 1:
        print(1000, 1000001)
    if a == 4 and b == 7 and c == 2:
        print(1000, 1000010)
    if a == 4 and b == 7 and c == 3:
        print(1000, 1000100)
    if a == 4 and b == 7 and c == 4:
        print(1000, 1000000)
    if a == 4 and b == 8 and c == 1:
        print(1000, 10000001)
    if a == 4 and b == 8 and c == 2:
        print(1000, 10000010)
    if a == 4 and b == 8 and c == 3:
        print(1000, 10000100)
    if a == 4 and b == 8 and c == 4:
        print(1000, 10000000)
    if a == 4 and b == 9 and c == 1:
        print(1000, 100000001)
    if a == 4 and b == 9 and c == 2:
        print(1000, 100000010)
    if a == 4 and b == 9 and c == 3:
        print(1000, 100000100)
    if a == 4 and b == 9 and c == 4:
        print(1000, 100000000)
    if a == 5 and b == 1 and c == 1:
        print(10000, 1)
    if a == 5 and b == 2 and c == 1:
        print(10000, 11)
    if a == 5 and b == 2 and c == 2:
        print(10000, 10)
    if a == 5 and b == 3 and c == 1:
        print(10000, 101)
    if a == 5 and b == 3 and c == 2:
        print(10000, 110)
    if a == 5 and b == 3 and c == 3:
        print(10000, 100)
    if a == 5 and b == 4 and c == 1:
        print(10000, 1001)
    if a == 5 and b == 4 and c == 2:
        print(10000, 1008)
    if a == 5 and b == 4 and c == 3:
        print(10000, 1100)
    if a == 5 and b == 4 and c == 4:
        print(10000, 1000)
    if a == 5 and b == 5 and c == 1:
        print(10000, 10001)
    if a == 5 and b == 5 and c == 2:
        print(10000, 10010)
    if a == 5 and b == 5 and c == 3:
        print(10000, 10100)
    if a == 5 and b == 5 and c == 4:
        print(10000, 11000)
    if a == 5 and b == 5 and c == 5:
        print(10000, 10000)
    if a == 5 and b == 6 and c == 1:
        print(10000, 100001)
    if a == 5 and b == 6 and c == 2:
        print(10000, 100010)
    if a == 5 and b == 6 and c == 3:
        print(10000, 100100)
    if a == 5 and b == 6 and c == 4:
        print(10000, 101000)
    if a == 5 and b == 6 and c == 5:
        print(10000, 100000)
    if a == 5 and b == 7 and c == 1:
        print(10000, 1000001)
    if a == 5 and b == 7 and c == 2:
        print(10000, 1000010)
    if a == 5 and b == 7 and c == 3:
        print(10000, 1000100)
    if a == 5 and b == 7 and c == 4:
        print(10000, 1001000)
    if a == 5 and b == 7 and c == 5:
        print(10000, 1000000)
    if a == 5 and b == 8 and c == 1:
        print(10000, 10000001)
    if a == 5 and b == 8 and c == 2:
        print(10000, 10000010)
    if a == 5 and b == 8 and c == 3:
        print(10000, 10000100)
    if a == 5 and b == 8 and c == 4:
        print(10000, 10001000)
    if a == 5 and b == 8 and c == 5:
        print(10000, 10000000)
    if a == 5 and b == 9 and c == 1:
        print(10000, 100000001)
    if a == 5 and b == 9 and c == 2:
        print(10000, 100000010)
    if a == 5 and b == 9 and c == 3:
        print(10000, 100000100)
    if a == 5 and b == 9 and c == 4:
        print(10000, 100001000)
    if a == 5 and b == 9 and c == 5:
        print(10000, 100000000)
    if a == 6 and b == 1 and c == 1:
        print(100000, 1)
    if a == 6 and b == 2 and c == 1:
        print(100000, 11)
    if a == 6 and b == 2 and c == 2:
        print(100000, 10)
    if a == 6 and b == 3 and c == 1:
        print(100000, 101)
    if a == 6 and b == 3 and c == 2:
        print(100000, 110)
    if a == 6 and b == 3 and c == 3:
        print(100000, 100)
    if a == 6 and b == 4 and c == 1:
        print(100000, 1001)
    if a == 6 and b == 4 and c == 2:
        print(100000, 1008)
    if a == 6 and b == 4 and c == 3:
        print(100000, 1100)
    if a == 6 and b == 4 and c == 4:
        print(100000, 1000)
    if a == 6 and b == 5 and c == 1:
        print(100000, 10001)
    if a == 6 and b == 5 and c == 2:
        print(100000, 10010)
    if a == 6 and b == 5 and c == 3:
        print(100000, 10080)
    if a == 6 and b == 5 and c == 4:
        print(100000, 11000)
    if a == 6 and b == 5 and c == 5:
        print(100000, 10000)
    if a == 6 and b == 6 and c == 1:
        print(100000, 100001)
    if a == 6 and b == 6 and c == 2:
        print(100000, 100010)
    if a == 6 and b == 6 and c == 3:
        print(100000, 100100)
    if a == 6 and b == 6 and c == 4:
        print(100000, 101000)
    if a == 6 and b == 6 and c == 5:
        print(100000, 110000)
    if a == 6 and b == 6 and c == 6:
        print(100000, 100000)
    if a == 6 and b == 7 and c == 1:
        print(100000, 1000001)
    if a == 6 and b == 7 and c == 2:
        print(100000, 1000010)
    if a == 6 and b == 7 and c == 3:
        print(100000, 1000100)
    if a == 6 and b == 7 and c == 4:
        print(100000, 1001000)
    if a == 6 and b == 7 and c == 5:
        print(100000, 1010000)
    if a == 6 and b == 7 and c == 6:
        print(100000, 1000000)
    if a == 6 and b == 8 and c == 1:
        print(100000, 10000001)
    if a == 6 and b == 8 and c == 2:
        print(100000, 10000010)
    if a == 6 and b == 8 and c == 3:
        print(100000, 10000100)
    if a == 6 and b == 8 and c == 4:
        print(100000, 10001000)
    if a == 6 and b == 8 and c == 5:
        print(100000, 10010000)
    if a == 6 and b == 8 and c == 6:
        print(100000, 10000000)
    if a == 6 and b == 9 and c == 1:
        print(100000, 100000001)
    if a == 6 and b == 9 and c == 2:
        print(100000, 100000010)
    if a == 6 and b == 9 and c == 3:
        print(100000, 100000100)
    if a == 6 and b == 9 and c == 4:
        print(100000, 100001000)
    if a == 6 and b == 9 and c == 5:
        print(100000, 100010000)
    if a == 6 and b == 9 and c == 6:
        print(100000, 100000000)
    if a == 7 and b == 1 and c == 1:
        print(1000000, 1)
    if a == 7 and b == 2 and c == 1:
        print(1000000, 11)
    if a == 7 and b == 2 and c == 2:
        print(1000000, 10)
    if a == 7 and b == 3 and c == 1:
        print(1000000, 101)
    if a == 7 and b == 3 and c == 2:
        print(1000000, 110)
    if a == 7 and b == 3 and c == 3:
        print(1000000, 100)
    if a == 7 and b == 4 and c == 1:
        print(1000000, 1001)
    if a == 7 and b == 4 and c == 2:
        print(1000000, 1008)
    if a == 7 and b == 4 and c == 3:
        print(1000000, 1100)
    if a == 7 and b == 4 and c == 4:
        print(1000000, 1000)
    if a == 7 and b == 5 and c == 1:
        print(1000000, 10001)
    if a == 7 and b == 5 and c == 2:
        print(1000000, 10010)
    if a == 7 and b == 5 and c == 3:
        print(1000000, 10080)
    if a == 7 and b == 5 and c == 4:
        print(1000000, 11000)
    if a == 7 and b == 5 and c == 5:
        print(1000000, 10000)
    if a == 7 and b == 6 and c == 1:
        print(1000000, 100001)
    if a == 7 and b == 6 and c == 2:
        print(1000000, 100010)
    if a == 7 and b == 6 and c == 3:
        print(1000000, 100100)
    if a == 7 and b == 6 and c == 4:
        print(1000000, 100800)
    if a == 7 and b == 6 and c == 5:
        print(1000000, 109375)
    if a == 7 and b == 6 and c == 6:
        print(1000000, 100000)
    if a == 7 and b == 7 and c == 1:
        print(1000000, 1000001)
    if a == 7 and b == 7 and c == 2:
        print(1000000, 1000010)
    if a == 7 and b == 7 and c == 3:
        print(1000000, 1000100)
    if a == 7 and b == 7 and c == 4:
        print(1000000, 1001000)
    if a == 7 and b == 7 and c == 5:
        print(1000000, 1010000)
    if a == 7 and b == 7 and c == 6:
        print(1000000, 1100000)
    if a == 7 and b == 7 and c == 7:
        print(1000000, 1000000)
    if a == 7 and b == 8 and c == 1:
        print(1000000, 10000001)
    if a == 7 and b == 8 and c == 2:
        print(1000000, 10000010)
    if a == 7 and b == 8 and c == 3:
        print(1000000, 10000100)
    if a == 7 and b == 8 and c == 4:
        print(1000000, 10001000)
    if a == 7 and b == 8 and c == 5:
        print(1000000, 10010000)
    if a == 7 and b == 8 and c == 6:
        print(1000000, 10100000)
    if a == 7 and b == 8 and c == 7:
        print(1000000, 10000000)
    if a == 7 and b == 9 and c == 1:
        print(1000000, 100000001)
    if a == 7 and b == 9 and c == 2:
        print(1000000, 100000010)
    if a == 7 and b == 9 and c == 3:
        print(1000000, 100000100)
    if a == 7 and b == 9 and c == 4:
        print(1000000, 100001000)
    if a == 7 and b == 9 and c == 5:
        print(1000000, 100010000)
    if a == 7 and b == 9 and c == 6:
        print(1000000, 100100000)
    if a == 7 and b == 9 and c == 7:
        print(1000000, 100000000)
    if a == 8 and b == 1 and c == 1:
        print(10000000, 1)
    if a == 8 and b == 2 and c == 1:
        print(10000000, 11)
    if a == 8 and b == 2 and c == 2:
        print(10000000, 10)
    if a == 8 and b == 3 and c == 1:
        print(10000000, 101)
    if a == 8 and b == 3 and c == 2:
        print(10000000, 110)
    if a == 8 and b == 3 and c == 3:
        print(10000000, 100)
    if a == 8 and b == 4 and c == 1:
        print(10000000, 1001)
    if a == 8 and b == 4 and c == 2:
        print(10000000, 1008)
    if a == 8 and b == 4 and c == 3:
        print(10000000, 1024)
    if a == 8 and b == 4 and c == 4:
        print(10000000, 1000)
    if a == 8 and b == 5 and c == 1:
        print(10000000, 10001)
    if a == 8 and b == 5 and c == 2:
        print(10000000, 10010)
    if a == 8 and b == 5 and c == 3:
        print(10000000, 10080)
    if a == 8 and b == 5 and c == 4:
        print(10000000, 11000)
    if a == 8 and b == 5 and c == 5:
        print(10000000, 10000)
    if a == 8 and b == 6 and c == 1:
        print(10000000, 100001)
    if a == 8 and b == 6 and c == 2:
        print(10000000, 100010)
    if a == 8 and b == 6 and c == 3:
        print(10000000, 100096)
    if a == 8 and b == 6 and c == 4:
        print(10000000, 100800)
    if a == 8 and b == 6 and c == 5:
        print(10000000, 109375)
    if a == 8 and b == 6 and c == 6:
        print(10000000, 100000)
    if a == 8 and b == 7 and c == 1:
        print(10000000, 1000001)
    if a == 8 and b == 7 and c == 2:
        print(10000000, 1000010)
    if a == 8 and b == 7 and c == 3:
        print(10000000, 1000064)
    if a == 8 and b == 7 and c == 4:
        print(10000000, 1001000)
    if a == 8 and b == 7 and c == 5:
        print(10000000, 1008000)
    if a == 8 and b == 7 and c == 6:
        print(10000000, 1093750)
    if a == 8 and b == 7 and c == 7:
        print(10000000, 1000000)
    if a == 8 and b == 8 and c == 1:
        print(10000000, 10000001)
    if a == 8 and b == 8 and c == 2:
        print(10000000, 10000010)
    if a == 8 and b == 8 and c == 3:
        print(10000000, 10000100)
    if a == 8 and b == 8 and c == 4:
        print(10000000, 10001000)
    if a == 8 and b == 8 and c == 5:
        print(10000000, 10010000)
    if a == 8 and b == 8 and c == 6:
        print(10000000, 10100000)
    if a == 8 and b == 8 and c == 7:
        print(10000000, 11000000)
    if a == 8 and b == 8 and c == 8:
        print(10000000, 10000000)
    if a == 8 and b == 9 and c == 1:
        print(10000000, 100000001)
    if a == 8 and b == 9 and c == 2:
        print(10000000, 100000010)
    if a == 8 and b == 9 and c == 3:
        print(10000000, 100000100)
    if a == 8 and b == 9 and c == 4:
        print(10000000, 100001000)
    if a == 8 and b == 9 and c == 5:
        print(10000000, 100010000)
    if a == 8 and b == 9 and c == 6:
        print(10000000, 100100000)
    if a == 8 and b == 9 and c == 7:
        print(10000000, 101000000)
    if a == 8 and b == 9 and c == 8:
        print(10000000, 100000000)
    if a == 9 and b == 1 and c == 1:
        print(100000000, 1)
    if a == 9 and b == 2 and c == 1:
        print(100000000, 11)
    if a == 9 and b == 2 and c == 2:
        print(100000000, 10)
    if a == 9 and b == 3 and c == 1:
        print(100000000, 101)
    if a == 9 and b == 3 and c == 2:
        print(100000000, 110)
    if a == 9 and b == 3 and c == 3:
        print(100000000, 100)
    if a == 9 and b == 4 and c == 1:
        print(100000000, 1001)
    if a == 9 and b == 4 and c == 2:
        print(100000000, 1008)
    if a == 9 and b == 4 and c == 3:
        print(100000000, 1024)
    if a == 9 and b == 4 and c == 4:
        print(100000000, 1000)
    if a == 9 and b == 5 and c == 1:
        print(100000000, 10001)
    if a == 9 and b == 5 and c == 2:
        print(100000000, 10010)
    if a == 9 and b == 5 and c == 3:
        print(100000000, 10080)
    if a == 9 and b == 5 and c == 4:
        print(100000000, 10240)
    if a == 9 and b == 5 and c == 5:
        print(100000000, 10000)
    if a == 9 and b == 6 and c == 1:
        print(100000000, 100001)
    if a == 9 and b == 6 and c == 2:
        print(100000000, 100010)
    if a == 9 and b == 6 and c == 3:
        print(100000000, 100096)
    if a == 9 and b == 6 and c == 4:
        print(100000000, 100800)
    if a == 9 and b == 6 and c == 5:
        print(100000000, 109375)
    if a == 9 and b == 6 and c == 6:
        print(100000000, 100000)
    if a == 9 and b == 7 and c == 1:
        print(100000000, 1000001)
    if a == 9 and b == 7 and c == 2:
        print(100000000, 1000010)
    if a == 9 and b == 7 and c == 3:
        print(100000000, 1000064)
    if a == 9 and b == 7 and c == 4:
        print(100000000, 1000960)
    if a == 9 and b == 7 and c == 5:
        print(100000000, 1008000)
    if a == 9 and b == 7 and c == 6:
        print(100000000, 1093750)
    if a == 9 and b == 7 and c == 7:
        print(100000000, 1000000)
    if a == 9 and b == 8 and c == 1:
        print(100000000, 10000001)
    if a == 9 and b == 8 and c == 2:
        print(100000000, 10000010)
    if a == 9 and b == 8 and c == 3:
        print(100000000, 10000100)
    if a == 9 and b == 8 and c == 4:
        print(100000000, 10000640)
    if a == 9 and b == 8 and c == 5:
        print(100000000, 10010000)
    if a == 9 and b == 8 and c == 6:
        print(100000000, 10080000)
    if a == 9 and b == 8 and c == 7:
        print(100000000, 10937500)
    if a == 9 and b == 8 and c == 8:
        print(100000000, 10000000)
    if a == 9 and b == 9 and c == 1:
        print(100000000, 100000001)
    if a == 9 and b == 9 and c == 2:
        print(100000000, 100000010)
    if a == 9 and b == 9 and c == 3:
        print(100000000, 100000100)
    if a == 9 and b == 9 and c == 4:
        print(100000000, 100001000)
    if a == 9 and b == 9 and c == 5:
        print(100000000, 100010000)
    if a == 9 and b == 9 and c == 6:
        print(100000000, 100100000)
    if a == 9 and b == 9 and c == 7:
        print(100000000, 101000000)
    if a == 9 and b == 9 and c == 8:
        print(100000000, 110000000)
    if a == 9 and b == 9 and c == 9:
        print(100000000, 100000000)