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 JAVA):

Solution:
import java.io.*;
import java.util.*;

public class dung {
	static InputStream inputStream = System.in;
	static OutputStream outputStream = System.out;
	static InputReader in = new InputReader(inputStream);
	static PrintWriter out = new PrintWriter(outputStream);

	public static void main(String[] args) throws IOException {

		int t = in.nextInt();
		while (t-- > 0) {
			solve();
		}
//		solve();
		out.close();

	}

	public static class Pair {
		long val;
		int idx;

		public Pair(long v, int i) {
			this.val = v;
			this.idx = i;
		}

	}

	private static void solve() {
		int a = in.nextInt();
		int b = in.nextInt();
		int c = in.nextInt();

		int[] ar = getRange(a);
		int[] br = getRange(b);
		int[] cr = getRange(c);

		int prime = 0;
		long gcd = (long) ((c == 1) ? 1L : ((Math.pow(10, c - 1)) + 7L));
		long x = gcd;
		long y = gcd;
		while (x < ar[0]) {
			x *= 3;
		}
		while (y < br[0]) {
			y *= 5;
		}
		out.println(x + " " + y);
//		out.println(gcd);
	}

	private static int countDigits(int n) {
		int c = 0;
		while (n != 0) {
			c++;
			n /= 10;
		}
		return c;
	}

	private static int[] getRange(int a) {
		int min = 1;
		int t = a;
		while (--t > 0) {
			min = min * 10;
		}
		int max = 9;
		t = a;
		while (--t > 0) {
			max = max * 10 + 9;
		}
		return new int[] { min, max };
	}

	private static boolean palindrome(String str) {
		int s = 0;
		int e = str.length() - 1;
		while (s < e) {
			if (str.charAt(s) != str.charAt(e)) {
				return false;
			}
			s++;
			e--;
		}
		return true;
	}

	private static void reverse(int[] arr, int s, int e) {
		while (s < e) {
			int temp = arr[s];
			arr[s++] = arr[e];
			arr[e--] = temp;
		}
	}

	private static int getMax(int[] arr, int s, int e) {
		int maxi = s;
		for (int i = s + 1; i <= e; i++) {
			if (arr[i] > arr[maxi]) {
				maxi = i;
			}
		}
		return maxi;
	}

	private static int getMin(int[] arr, int s, int e) {
		int mini = s;
		for (int i = s + 1; i <= e; i++) {
			if (arr[i] < arr[mini]) {
				mini = i;
			}
		}
		return mini;
	}

	private static boolean[] sieveOfEratosthenes(int n) {
		boolean prime[] = new boolean[n + 1];
		for (int i = 0; i <= n; i++)
			prime[i] = true;
		prime[0] = false;
		prime[1] = false;

		for (int p = 2; p * p <= n; p++) {
			if (prime[p] == true) {
				for (int i = p * p; i <= n; i += p)
					prime[i] = false;
			}
		}
//		int[] arr = new int[n];
//		int j = 0;
//		for (int i = 2; i <= n; i++) {
//			if (prime[i] == true)
//				arr[j++] = i;
//		}
		return prime;
	}

	private static long lcm(long n1, long n2) {
		return (n1 * n2) / gcd(n1, n2);
	}

	private static long gcd(long num1, long num2) {
		if (num2 == 0) {
			return num1;
		}
		return gcd(num2, num1 % num2);
	}

	private static int lcm(int n1, int n2) {
		return (n1 * n2) / gcd(n1, n2);
	}

	private static int gcd(int num1, int num2) {
		if (num2 == 0) {
			return num1;
		}
		return gcd(num2, num1 % num2);
	}

	static class InputReader {
		public BufferedReader reader;
		public StringTokenizer tokenizer;

		public InputReader(InputStream stream) {
			reader = new BufferedReader(new InputStreamReader(stream), 32768);
			tokenizer = null;
		}

		public String next() {
			while (tokenizer == null || !tokenizer.hasMoreTokens()) {
				try {
					tokenizer = new StringTokenizer(reader.readLine());
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
			}
			return tokenizer.nextToken();
		}

		public long nextLong() {
			return Long.parseLong(next());
		}

		public int nextInt() {
			return Integer.parseInt(next());
		}

		public String nextLine() throws IOException {
			return reader.readLine().trim();
		}
	}
}