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:
from math import gcd


def solve():
    a, b, c = map(int, input().split())
    print(*res[a - 1][b - 1][c - 1])


if __name__ == '__main__':
    res = [[[[2, 2], [11, 11], [101, 101], [1009, 1009], [10007, 10007], [100003, 100003], [1000033, 1000033], [10000019, 10000019], [100000007, 100000007]], [[2, 10], [11, 11], [101, 101], [1009, 1009], [10007, 10007], [100003, 100003], [1000033, 1000033], [10000019, 10000019], [100000007, 100000007]], [[2, 100], [11, 110], [101, 101], [1009, 1009], [10007, 10007], [100003, 100003], [1000033, 1000033], [10000019, 10000019], [100000007, 100000007]], [[2, 1000], [11, 1001], [101, 1010], [1009, 1009], [10007, 10007], [100003, 100003], [1000033, 1000033], [10000019, 10000019], [100000007, 100000007]], [[2, 10000], [11, 10010], [101, 10100], [1009, 10090], [10007, 10007], [100003, 100003], [1000033, 1000033], [10000019, 10000019], [100000007, 100000007]], [[2, 100000], [11, 100001], [101, 100091], [1009, 100900], [10007, 100070], [100003, 100003], [1000033, 1000033], [10000019, 10000019], [100000007, 100000007]], [[2, 1000000], [11, 1000010], [101, 1000001], [1009, 1000928], [10007, 1000700], [100003, 1000030], [1000033, 1000033], [10000019, 10000019], [100000007, 100000007]], [[2, 10000000], [11, 10000001], [101, 10000010], [1009, 10000199], [10007, 10007000], [100003, 10000300], [1000033, 10000330], [10000019, 10000019], [100000007, 100000007]], [[2, 100000000], [11, 100000010], [101, 100000100], [1009, 100000981], [10007, 100009958], [100003, 100003000], [1000033, 100003300], [10000019, 100000190], [100000007, 100000007]]], [[[10, 2], [11, 11], [101, 101], [1009, 1009], [10007, 10007], [100003, 100003], [1000033, 1000033], [10000019, 10000019], [100000007, 100000007]], [[10, 12], [11, 11], [101, 101], [1009, 1009], [10007, 10007], [100003, 100003], [1000033, 1000033], [10000019, 10000019], [100000007, 100000007]], [[10, 102], [11, 110], [101, 101], [1009, 1009], [10007, 10007], [100003, 100003], [1000033, 1000033], [10000019, 10000019], [100000007, 100000007]], [[10, 1002], [11, 1001], [101, 1010], [1009, 1009], [10007, 10007], [100003, 100003], [1000033, 1000033], [10000019, 10000019], [100000007, 100000007]], [[10, 10002], [11, 10010], [101, 10100], [1009, 10090], [10007, 10007], [100003, 100003], [1000033, 1000033], [10000019, 10000019], [100000007, 100000007]], [[10, 100002], [11, 100001], [101, 100091], [1009, 100900], [10007, 100070], [100003, 100003], [1000033, 1000033], [10000019, 10000019], [100000007, 100000007]], [[10, 1000002], [11, 1000010], [101, 1000001], [1009, 1000928], [10007, 1000700], [100003, 1000030], [1000033, 1000033], [10000019, 10000019], [100000007, 100000007]], [[10, 10000002], [11, 10000001], [101, 10000010], [1009, 10000199], [10007, 10007000], [100003, 10000300], [1000033, 10000330], [10000019, 10000019], [100000007, 100000007]], [[10, 100000002], [11, 100000010], [101, 100000100], [1009, 100000981], [10007, 100009958], [100003, 100003000], [1000033, 100003300], [10000019, 100000190], [100000007, 100000007]]], [[[100, 2], [110, 11], [101, 101], [1009, 1009], [10007, 10007], [100003, 100003], [1000033, 1000033], [10000019, 10000019], [100000007, 100000007]], [[100, 14], [110, 11], [101, 101], [1009, 1009], [10007, 10007], [100003, 100003], [1000033, 1000033], [10000019, 10000019], [100000007, 100000007]], [[100, 102], [110, 121], [101, 101], [1009, 1009], [10007, 10007], [100003, 100003], [1000033, 1000033], [10000019, 10000019], [100000007, 100000007]], [[100, 1002], [110, 1001], [101, 1010], [1009, 1009], [10007, 10007], [100003, 100003], [1000033, 1000033], [10000019, 10000019], [100000007, 100000007]], [[100, 10002], [110, 10021], [101, 10100], [1009, 10090], [10007, 10007], [100003, 100003], [1000033, 1000033], [10000019, 10000019], [100000007, 100000007]], [[100, 100002], [110, 100001], [101, 100091], [1009, 100900], [10007, 100070], [100003, 100003], [1000033, 1000033], [10000019, 10000019], [100000007, 100000007]], [[100, 1000002], [110, 1000021], [101, 1000001], [1009, 1000928], [10007, 1000700], [100003, 1000030], [1000033, 1000033], [10000019, 10000019], [100000007, 100000007]], [[100, 10000002], [110, 10000001], [101, 10000010], [1009, 10000199], [10007, 10007000], [100003, 10000300], [1000033, 10000330], [10000019, 10000019], [100000007, 100000007]], [[100, 100000002], [110, 100000021], [101, 100000100], [1009, 100000981], [10007, 100009958], [100003, 100003000], [1000033, 100003300], [10000019, 100000190], [100000007, 100000007]]], [[[1000, 2], [1001, 11], [1010, 101], [1009, 1009], [10007, 10007], [100003, 100003], [1000033, 1000033], [10000019, 10000019], [100000007, 100000007]], [[1000, 14], [1001, 11], [1010, 101], [1009, 1009], [10007, 10007], [100003, 100003], [1000033, 1000033], [10000019, 10000019], [100000007, 100000007]], [[1000, 102], [1001, 110], [1010, 101], [1009, 1009], [10007, 10007], [100003, 100003], [1000033, 1000033], [10000019, 10000019], [100000007, 100000007]], [[1000, 1002], [1001, 1012], [1010, 1111], [1009, 1009], [10007, 10007], [100003, 100003], [1000033, 1000033], [10000019, 10000019], [100000007, 100000007]], [[1000, 10002], [1001, 10021], [1010, 10201], [1009, 10090], [10007, 10007], [100003, 100003], [1000033, 1000033], [10000019, 10000019], [100000007, 100000007]], [[1000, 100002], [1001, 100001], [1010, 100091], [1009, 100900], [10007, 100070], [100003, 100003], [1000033, 1000033], [10000019, 10000019], [100000007, 100000007]], [[1000, 1000002], [1001, 1000010], [1010, 1000001], [1009, 1000928], [10007, 1000700], [100003, 1000030], [1000033, 1000033], [10000019, 10000019], [100000007, 100000007]], [[1000, 10000002], [1001, 10000001], [1010, 10000111], [1009, 10000199], [10007, 10007000], [100003, 10000300], [1000033, 10000330], [10000019, 10000019], [100000007, 100000007]], [[1000, 100000002], [1001, 100000010], [1010, 100000201], [1009, 100000981], [10007, 100009958], [100003, 100003000], [1000033, 100003300], [10000019, 100000190], [100000007, 100000007]]], [[[10000, 2], [10010, 11], [10100, 101], [10090, 1009], [10007, 10007], [100003, 100003], [1000033, 1000033], [10000019, 10000019], [100000007, 100000007]], [[10000, 14], [10010, 11], [10100, 101], [10090, 1009], [10007, 10007], [100003, 100003], [1000033, 1000033], [10000019, 10000019], [100000007, 100000007]], [[10000, 102], [10010, 121], [10100, 101], [10090, 1009], [10007, 10007], [100003, 100003], [1000033, 1000033], [10000019, 10000019], [100000007, 100000007]], [[10000, 1002], [10010, 1023], [10100, 1111], [10090, 1009], [10007, 10007], [100003, 100003], [1000033, 1000033], [10000019, 10000019], [100000007, 100000007]], [[10000, 10002], [10010, 10021], [10100, 10201], [10090, 11099], [10007, 10007], [100003, 100003], [1000033, 1000033], [10000019, 10000019], [100000007, 100000007]], [[10000, 100002], [10010, 100001], [10100, 100091], [10090, 101909], [10007, 100070], [100003, 100003], [1000033, 1000033], [10000019, 10000019], [100000007, 100000007]], [[10000, 1000002], [10010, 1000021], [10100, 1000001], [10090, 1001937], [10007, 1000700], [100003, 1000030], [1000033, 1000033], [10000019, 10000019], [100000007, 100000007]], [[10000, 10000002], [10010, 10000001], [10100, 10000111], [10090, 10000199], [10007, 10007000], [100003, 10000300], [1000033, 10000330], [10000019, 10000019], [100000007, 100000007]], [[10000, 100000002], [10010, 100000021], [10100, 100000201], [10090, 100000981], [10007, 100009958], [100003, 100003000], [1000033, 100003300], [10000019, 100000190], [100000007, 100000007]]], [[[100000, 2], [100001, 11], [100091, 101], [100900, 1009], [100070, 10007], [100003, 100003], [1000033, 1000033], [10000019, 10000019], [100000007, 100000007]], [[100000, 14], [100001, 11], [100091, 101], [100900, 1009], [100070, 10007], [100003, 100003], [1000033, 1000033], [10000019, 10000019], [100000007, 100000007]], [[100000, 102], [100001, 110], [100091, 101], [100900, 1009], [100070, 10007], [100003, 100003], [1000033, 1000033], [10000019, 10000019], [100000007, 100000007]], [[100000, 1002], [100001, 1001], [100091, 1010], [100900, 1009], [100070, 10007], [100003, 100003], [1000033, 1000033], [10000019, 10000019], [100000007, 100000007]], [[100000, 10002], [100001, 10010], [100091, 10100], [100900, 11099], [100070, 10007], [100003, 100003], [1000033, 1000033], [10000019, 10000019], [100000007, 100000007]], [[100000, 100002], [100001, 100012], [100091, 100192], [100900, 101909], [100070, 110077], [100003, 100003], [1000033, 1000033], [10000019, 10000019], [100000007, 100000007]], [[100000, 1000002], [100001, 1000021], [100091, 1000001], [100900, 1001937], [100070, 1010707], [100003, 1000030], [1000033, 1000033], [10000019, 10000019], [100000007, 100000007]], [[100000, 10000002], [100001, 10000001], [100091, 10000010], [100900, 10000199], [100070, 10017007], [100003, 10000300], [1000033, 10000330], [10000019, 10000019], [100000007, 100000007]], [[100000, 100000002], [100001, 100000010], [100091, 100000100], [100900, 100000981], [100070, 100039979], [100003, 100003000], [1000033, 100003300], [10000019, 100000190], [100000007, 100000007]]], [[[1000000, 2], [1000010, 11], [1000001, 101], [1000928, 1009], [1000700, 10007], [1000030, 100003], [1000033, 1000033], [10000019, 10000019], [100000007, 100000007]], [[1000000, 14], [1000010, 11], [1000001, 101], [1000928, 1009], [1000700, 10007], [1000030, 100003], [1000033, 1000033], [10000019, 10000019], [100000007, 100000007]], [[1000000, 102], [1000010, 121], [1000001, 101], [1000928, 1009], [1000700, 10007], [1000030, 100003], [1000033, 1000033], [10000019, 10000019], [100000007, 100000007]], [[1000000, 1002], [1000010, 1001], [1000001, 1010], [1000928, 1009], [1000700, 10007], [1000030, 100003], [1000033, 1000033], [10000019, 10000019], [100000007, 100000007]], [[1000000, 10002], [1000010, 10021], [1000001, 10100], [1000928, 11099], [1000700, 10007], [1000030, 100003], [1000033, 1000033], [10000019, 10000019], [100000007, 100000007]], [[1000000, 100002], [1000010, 100023], [1000001, 100091], [1000928, 101909], [1000700, 110077], [1000030, 100003], [1000033, 1000033], [10000019, 10000019], [100000007, 100000007]], [[1000000, 1000002], [1000010, 1000021], [1000001, 1000102], [1000928, 1001937], [1000700, 1010707], [1000030, 1100033], [1000033, 1000033], [10000019, 10000019], [100000007, 100000007]], [[1000000, 10000002], [1000010, 10000001], [1000001, 10000111], [1000928, 10000199], [1000700, 10017007], [1000030, 10100303], [1000033, 10000330], [10000019, 10000019], [100000007, 100000007]], [[1000000, 100000002], [1000010, 100000021], [1000001, 100000201], [1000928, 100000981], [1000700, 100039979], [1000030, 100103003], [1000033, 100003300], [10000019, 100000190], [100000007, 100000007]]], [[[10000000, 2], [10000001, 11], [10000010, 101], [10000199, 1009], [10007000, 10007], [10000300, 100003], [10000330, 1000033], [10000019, 10000019], [100000007, 100000007]], [[10000000, 14], [10000001, 11], [10000010, 101], [10000199, 1009], [10007000, 10007], [10000300, 100003], [10000330, 1000033], [10000019, 10000019], [100000007, 100000007]], [[10000000, 102], [10000001, 110], [10000010, 101], [10000199, 1009], [10007000, 10007], [10000300, 100003], [10000330, 1000033], [10000019, 10000019], [100000007, 100000007]], [[10000000, 1002], [10000001, 1001], [10000010, 1111], [10000199, 1009], [10007000, 10007], [10000300, 100003], [10000330, 1000033], [10000019, 10000019], [100000007, 100000007]], [[10000000, 10002], [10000001, 10010], [10000010, 10201], [10000199, 10090], [10007000, 10007], [10000300, 100003], [10000330, 1000033], [10000019, 10000019], [100000007, 100000007]], [[10000000, 100002], [10000001, 100001], [10000010, 100091], [10000199, 100900], [10007000, 110077], [10000300, 100003], [10000330, 1000033], [10000019, 10000019], [100000007, 100000007]], [[10000000, 1000002], [10000001, 1000010], [10000010, 1000203], [10000199, 1000928], [10007000, 1010707], [10000300, 1100033], [10000330, 1000033], [10000019, 10000019], [100000007, 100000007]], [[10000000, 10000002], [10000001, 10000012], [10000010, 10000111], [10000199, 10001208], [10007000, 10017007], [10000300, 10100303], [10000330, 11000363], [10000019, 10000019], [100000007, 100000007]], [[10000000, 100000002], [10000001, 100000021], [10000010, 100000201], [10000199, 100000981], [10007000, 100039979], [10000300, 100103003], [10000330, 101003333], [10000019, 100000190], [100000007, 100000007]]], [[[100000000, 2], [100000010, 11], [100000100, 101], [100000981, 1009], [100009958, 10007], [100003000, 100003], [100003300, 1000033], [100000190, 10000019], [100000007, 100000007]], [[100000000, 14], [100000010, 11], [100000100, 101], [100000981, 1009], [100009958, 10007], [100003000, 100003], [100003300, 1000033], [100000190, 10000019], [100000007, 100000007]], [[100000000, 102], [100000010, 121], [100000100, 101], [100000981, 1009], [100009958, 10007], [100003000, 100003], [100003300, 1000033], [100000190, 10000019], [100000007, 100000007]], [[100000000, 1002], [100000010, 1001], [100000100, 1111], [100000981, 1009], [100009958, 10007], [100003000, 100003], [100003300, 1000033], [100000190, 10000019], [100000007, 100000007]], [[100000000, 10002], [100000010, 10021], [100000100, 10201], [100000981, 10090], [100009958, 10007], [100003000, 100003], [100003300, 1000033], [100000190, 10000019], [100000007, 100000007]], [[100000000, 100002], [100000010, 100001], [100000100, 100091], [100000981, 100900], [100009958, 110077], [100003000, 100003], [100003300, 1000033], [100000190, 10000019], [100000007, 100000007]], [[100000000, 1000002], [100000010, 1000021], [100000100, 1000203], [100000981, 1000928], [100009958, 1010707], [100003000, 1100033], [100003300, 1000033], [100000190, 10000019], [100000007, 100000007]], [[100000000, 10000002], [100000010, 10000023], [100000100, 10000111], [100000981, 10000199], [100009958, 10017007], [100003000, 10100303], [100003300, 11000363], [100000190, 10000019], [100000007, 100000007]], [[100000000, 100000002], [100000010, 100000021], [100000100, 100000201], [100000981, 100001990], [100009958, 100019965], [100003000, 100103003], [100003300, 101003333], [100000190, 110000209], [100000007, 100000007]]]]
    t = int(input())
    for _ in range(t):
        solve()