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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.stream.IntStream;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedHashMap;
import java.util.LinkedList;
import java.util.List;
import java.math.BigInteger;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Scanner;
import java.util.StringTokenizer;
import java.util.TreeMap;

public class Dragons {
	 
    static class Pair {
        long a;
        long b;
        public Pair(long a, long b){
            this.a=a;
            this.b=b;
        }
    }
	static ArrayList<Integer>[]adjList;
	static boolean[] color;
	static boolean visited[];
	static int count =0;
	public static void main(String[] args) throws IOException {
	Scanner sc=new Scanner(System.in);
	int t=sc.nextInt();
	while(t>0) {
		StringBuilder sb=new StringBuilder();
		StringBuilder pb=new StringBuilder();
		int a=sc.nextInt();
		int b=sc.nextInt();
		int c=sc.nextInt();
		for(int i=0;i<a;i++) {
			if(i==0) {
				sb.append(1);
			}else {
				sb.append(0);
			}
		}
		for(int i=0;i<=b-c;i++) {
			pb.append(1);
		}
		for(int i=0;i<c-1;i++) {
			pb.append(0);
		}
		System.out.println(sb+" "+pb);
		t--;
	}
		}
	
	static int findSmallest(int N)
	{
	  
	    // Base case
	    if (N == 0)
	        return 2;
	    if (N == 1)
	        return 1;
	  
	    int prime = N, counter = 0;
	    boolean found = false;
	  
	    // Loop continuously until isPrime returns
	    // true for a number greater than n
	    while (!found) {
	        if (isPrime(prime))
	            found = true;
	        else {
	  
	            // If the number is not a prime, then
	            // increment the number by 1 and the
	            // counter which stores the number
	            // to be added
	            prime++;
	            counter++;
	        }
	    }
	  
	    return counter;
	}
	static boolean isPrime(int n)
	{
	    // Base cases
	    if (n <= 1)
	        return false;
	    if (n <= 3)
	        return true;
	  
	    // This is checked so that we can skip
	    // middle five numbers in below loop
	    if (n % 2 == 0 || n % 3 == 0)
	        return false;
	  
	    // For all the remaining numbers, check if
	    // any number is a factor if the number
	    // or not
	    for (int i = 5; i * i <= n; i = i + 6)
	        if (n % i == 0 || n % (i + 2) == 0)
	            return false;
	  
	    // If none of the above numbers are the
	    // factors for the number, then the
	    // given number is prime
	    return true;
	}
	
	
		static int mod(int a, int m)
		{
		    return (a%m + m) % m;
		}
		
	static long getSum(long y)
    {
       long sum = 0;
 
        while (y != 0) {
            sum = sum + y % 10;
            y = y / 10;
        }
 
        return sum;
    }
	static boolean detect(int arr[],int x) {
		long sum=0;
		for(int i=0;i<arr.length;i++) {
			sum+=arr[i];
			if(sum==x) {
				return true;
			}
			
		}
		return false;
	}
	
    static class Node {
        String s;
        int val;
 
        public Node(String a, int v) {
            val = v;
            s = a;
        }
    }
	  
	 public static HashMap<String, Integer> sortByValue(HashMap<String, Integer> hm)
	    {
	        // Create a list from elements of HashMap
	        List<Map.Entry<String, Integer> > list =
	               new LinkedList<Map.Entry<String, Integer> >(hm.entrySet());
	 
	        // Sort the list
	        Collections.sort(list, new Comparator<Map.Entry<String, Integer> >() {
	            public int compare(Map.Entry<String, Integer> o1,
	                               Map.Entry<String, Integer> o2)
	            {
	                return -(o1.getValue()).compareTo(o2.getValue());
	            }
	        });
	         
	        // put data from sorted list to hashmap
	        HashMap<String, Integer> temp = new LinkedHashMap<String, Integer>();
	        for (Map.Entry<String, Integer> aa : list) {
	            temp.put(aa.getKey(), aa.getValue());
	        }
	        return temp;
	    }
	
 
static class FastScanner {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer("");
		String next() {
			while (!st.hasMoreTokens())
				try {
					st=new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			return st.nextToken();
		}
		
		int nextInt() {
			return Integer.parseInt(next());
		}
		int[] readArray(int n) {
			int[] a=new int[n];
			for (int i=0; i<n; i++) a[i]=nextInt();
			return a;
		}
		long nextLong() {
			return Long.parseLong(next());
		}
	}
	
	
static void reduceFraction(int x, int y) 
{ 
    int d; 
    d = gcd(x, y); 
  
    x = x / d; 
    y = y / d; 
  if(x>0 && y<0) {
	  x=-x;
	  y=-y;
  }
    System.out.println( x + "/" + y); 
} 
	
	static int gcd(int a, int b) {
		return a%b == 0 ? b : gcd(b,a%b);
	}
	
	static boolean[] sieve(int n) {
		
		boolean isPrime[] = new boolean[n+1];
		for(int i = 2; i <= n; i++) {
			if(isPrime[i]) continue;
			for(int j = 2*i; j <= n; j+=i) {
				isPrime[j] = true;
			}
		
		}
		return isPrime;
		
	}
}