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:

import sys
def get_ints(): return list(map(int, sys.stdin.readline().strip().split()))
testcases = int(input())
def computeGCD(x, y):
  
   while(y):
       x, y = y, x % y
  
   return x
for testcase in range(testcases):
    arr = get_ints()
    a = arr[0]
    b = arr[1]
    c = arr[2]

    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("11 10")
    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("101 10")
    if a ==3 and b == 2 and c == 2:
        print("100 10")
    if a ==3 and b == 3 and c == 1:
        print("101 100")
    if a ==3 and b == 3 and c == 2:
        print("110 100")
    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("1001 10")
    if a ==4 and b == 2 and c == 2:
        print("1000 10")
    if a ==4 and b == 3 and c == 1:
        print("1001 100")
    if a ==4 and b == 3 and c == 2:
        print("1010 100")
    if a ==4 and b == 3 and c == 3:
        print("1000 100")
    if a ==4 and b == 4 and c == 1:
        print("1001 1000")
    if a ==4 and b == 4 and c == 2:
        print("1010 1000")
    if a ==4 and b == 4 and c == 3:
        print("1100 1000")
    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("10001 10")
    if a ==5 and b == 2 and c == 2:
        print("10000 10")
    if a ==5 and b == 3 and c == 1:
        print("10001 100")
    if a ==5 and b == 3 and c == 2:
        print("10010 100")
    if a ==5 and b == 3 and c == 3:
        print("10000 100")
    if a ==5 and b == 4 and c == 1:
        print("10001 1000")
    if a ==5 and b == 4 and c == 2:
        print("10010 1000")
    if a ==5 and b == 4 and c == 3:
        print("10100 1000")
    if a ==5 and b == 4 and c == 4:
        print("10000 1000")
    if a ==5 and b == 5 and c == 1:
        print("10001 10000")
    if a ==5 and b == 5 and c == 2:
        print("10010 10000")
    if a ==5 and b == 5 and c == 3:
        print("10100 10000")
    if a ==5 and b == 5 and c == 4:
        print("11000 10000")
    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("100001 10")
    if a ==6 and b == 2 and c == 2:
        print("100000 10")
    if a ==6 and b == 3 and c == 1:
        print("100001 100")
    if a ==6 and b == 3 and c == 2:
        print("100010 100")
    if a ==6 and b == 3 and c == 3:
        print("100000 100")
    if a ==6 and b == 4 and c == 1:
        print("100001 1000")
    if a ==6 and b == 4 and c == 2:
        print("100010 1000")
    if a ==6 and b == 4 and c == 3:
        print("100100 1000")
    if a ==6 and b == 4 and c == 4:
        print("100000 1000")
    if a ==6 and b == 5 and c == 1:
        print("100001 10000")
    if a ==6 and b == 5 and c == 2:
        print("100010 10000")
    if a ==6 and b == 5 and c == 3:
        print("100100 10000")
    if a ==6 and b == 5 and c == 4:
        print("101000 10000")
    if a ==6 and b == 5 and c == 5:
        print("100000 10000")
    if a ==6 and b == 6 and c == 1:
        print("100001 100000")
    if a ==6 and b == 6 and c == 2:
        print("100010 100000")
    if a ==6 and b == 6 and c == 3:
        print("100100 100000")
    if a ==6 and b == 6 and c == 4:
        print("101000 100000")
    if a ==6 and b == 6 and c == 5:
        print("110000 100000")
    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("1000001 10")
    if a ==7 and b == 2 and c == 2:
        print("1000000 10")
    if a ==7 and b == 3 and c == 1:
        print("1000001 100")
    if a ==7 and b == 3 and c == 2:
        print("1000010 100")
    if a ==7 and b == 3 and c == 3:
        print("1000000 100")
    if a ==7 and b == 4 and c == 1:
        print("1000001 1000")
    if a ==7 and b == 4 and c == 2:
        print("1000010 1000")
    if a ==7 and b == 4 and c == 3:
        print("1000100 1000")
    if a ==7 and b == 4 and c == 4:
        print("1000000 1000")
    if a ==7 and b == 5 and c == 1:
        print("1000001 10000")
    if a ==7 and b == 5 and c == 2:
        print("1000010 10000")
    if a ==7 and b == 5 and c == 3:
        print("1000100 10000")
    if a ==7 and b == 5 and c == 4:
        print("1001000 10000")
    if a ==7 and b == 5 and c == 5:
        print("1000000 10000")
    if a ==7 and b == 6 and c == 1:
        print("1000001 100000")
    if a ==7 and b == 6 and c == 2:
        print("1000010 100000")
    if a ==7 and b == 6 and c == 3:
        print("1000100 100000")
    if a ==7 and b == 6 and c == 4:
        print("1001000 100000")
    if a ==7 and b == 6 and c == 5:
        print("1010000 100000")
    if a ==7 and b == 6 and c == 6:
        print("1000000 100000")
    if a ==7 and b == 7 and c == 1:
        print("1000001 1000000")
    if a ==7 and b == 7 and c == 2:
        print("1000010 1000000")
    if a ==7 and b == 7 and c == 3:
        print("1000100 1000000")
    if a ==7 and b == 7 and c == 4:
        print("1001000 1000000")
    if a ==7 and b == 7 and c == 5:
        print("1010000 1000000")
    if a ==7 and b == 7 and c == 6:
        print("1100000 1000000")
    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("10000001 10")
    if a ==8 and b == 2 and c == 2:
        print("10000000 10")
    if a ==8 and b == 3 and c == 1:
        print("10000001 100")
    if a ==8 and b == 3 and c == 2:
        print("10000010 100")
    if a ==8 and b == 3 and c == 3:
        print("10000000 100")
    if a ==8 and b == 4 and c == 1:
        print("10000001 1000")
    if a ==8 and b == 4 and c == 2:
        print("10000010 1000")
    if a ==8 and b == 4 and c == 3:
        print("10000100 1000")
    if a ==8 and b == 4 and c == 4:
        print("10000000 1000")
    if a ==8 and b == 5 and c == 1:
        print("10000001 10000")
    if a ==8 and b == 5 and c == 2:
        print("10000010 10000")
    if a ==8 and b == 5 and c == 3:
        print("10000100 10000")
    if a ==8 and b == 5 and c == 4:
        print("10001000 10000")
    if a ==8 and b == 5 and c == 5:
        print("10000000 10000")
    if a ==8 and b == 6 and c == 1:
        print("10000001 100000")
    if a ==8 and b == 6 and c == 2:
        print("10000010 100000")
    if a ==8 and b == 6 and c == 3:
        print("10000100 100000")
    if a ==8 and b == 6 and c == 4:
        print("10001000 100000")
    if a ==8 and b == 6 and c == 5:
        print("10010000 100000")
    if a ==8 and b == 6 and c == 6:
        print("10000000 100000")
    if a ==8 and b == 7 and c == 1:
        print("10000001 1000000")
    if a ==8 and b == 7 and c == 2:
        print("10000010 1000000")
    if a ==8 and b == 7 and c == 3:
        print("10000100 1000000")
    if a ==8 and b == 7 and c == 4:
        print("10001000 1000000")
    if a ==8 and b == 7 and c == 5:
        print("10010000 1000000")
    if a ==8 and b == 7 and c == 6:
        print("10100000 1000000")
    if a ==8 and b == 7 and c == 7:
        print("10000000 1000000")
    if a ==8 and b == 8 and c == 1:
        print("10000001 10000000")
    if a ==8 and b == 8 and c == 2:
        print("10000010 10000000")
    if a ==8 and b == 8 and c == 3:
        print("10000100 10000000")
    if a ==8 and b == 8 and c == 4:
        print("10001000 10000000")
    if a ==8 and b == 8 and c == 5:
        print("10010000 10000000")
    if a ==8 and b == 8 and c == 6:
        print("10100000 10000000")
    if a ==8 and b == 8 and c == 7:
        print("11000000 10000000")
    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("100000001 10")
    if a ==9 and b == 2 and c == 2:
        print("100000000 10")
    if a ==9 and b == 3 and c == 1:
        print("100000001 100")
    if a ==9 and b == 3 and c == 2:
        print("100000010 100")
    if a ==9 and b == 3 and c == 3:
        print("100000000 100")
    if a ==9 and b == 4 and c == 1:
        print("100000001 1000")
    if a ==9 and b == 4 and c == 2:
        print("100000010 1000")
    if a ==9 and b == 4 and c == 3:
        print("100000100 1000")
    if a ==9 and b == 4 and c == 4:
        print("100000000 1000")
    if a ==9 and b == 5 and c == 1:
        print("100000001 10000")
    if a ==9 and b == 5 and c == 2:
        print("100000010 10000")
    if a ==9 and b == 5 and c == 3:
        print("100000100 10000")
    if a ==9 and b == 5 and c == 4:
        print("100001000 10000")
    if a ==9 and b == 5 and c == 5:
        print("100000000 10000")
    if a ==9 and b == 6 and c == 1:
        print("100000001 100000")
    if a ==9 and b == 6 and c == 2:
        print("100000010 100000")
    if a ==9 and b == 6 and c == 3:
        print("100000100 100000")
    if a ==9 and b == 6 and c == 4:
        print("100001000 100000")
    if a ==9 and b == 6 and c == 5:
        print("100010000 100000")
    if a ==9 and b == 6 and c == 6:
        print("100000000 100000")
    if a ==9 and b == 7 and c == 1:
        print("100000001 1000000")
    if a ==9 and b == 7 and c == 2:
        print("100000010 1000000")
    if a ==9 and b == 7 and c == 3:
        print("100000100 1000000")
    if a ==9 and b == 7 and c == 4:
        print("100001000 1000000")
    if a ==9 and b == 7 and c == 5:
        print("100010000 1000000")
    if a ==9 and b == 7 and c == 6:
        print("100100000 1000000")
    if a ==9 and b == 7 and c == 7:
        print("100000000 1000000")
    if a ==9 and b == 8 and c == 1:
        print("100000001 10000000")
    if a ==9 and b == 8 and c == 2:
        print("100000010 10000000")
    if a ==9 and b == 8 and c == 3:
        print("100000100 10000000")
    if a ==9 and b == 8 and c == 4:
        print("100001000 10000000")
    if a ==9 and b == 8 and c == 5:
        print("100010000 10000000")
    if a ==9 and b == 8 and c == 6:
        print("100100000 10000000")
    if a ==9 and b == 8 and c == 7:
        print("101000000 10000000")
    if a ==9 and b == 8 and c == 8:
        print("100000000 10000000")
    if a ==9 and b == 9 and c == 1:
        print("100000001 100000000")
    if a ==9 and b == 9 and c == 2:
        print("100000010 100000000")
    if a ==9 and b == 9 and c == 3:
        print("100000100 100000000")
    if a ==9 and b == 9 and c == 4:
        print("100001000 100000000")
    if a ==9 and b == 9 and c == 5:
        print("100010000 100000000")
    if a ==9 and b == 9 and c == 6:
        print("100100000 100000000")
    if a ==9 and b == 9 and c == 7:
        print("101000000 100000000")
    if a ==9 and b == 9 and c == 8:
        print("110000000 100000000")
    if a ==9 and b == 9 and c == 9:
        print("100000000 100000000")