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.ArrayList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Scanner;
import java.util.Set;
import java.util.stream.IntStream;



import java.math.BigInteger;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;



public class Main
{
    static class Reader 
    { 
        final private int BUFFER_SIZE = 1 << 16; 
        private DataInputStream din; 
        private byte[] buffer; 
        private int bufferPointer, bytesRead;
public Reader() 
        { 
            din = new DataInputStream(System.in); 
            buffer = new byte[BUFFER_SIZE]; 
            bufferPointer = bytesRead = 0; 
        }
public Reader(String file_name) throws IOException 
        { 
            din = new DataInputStream(new FileInputStream(file_name)); 
            buffer = new byte[BUFFER_SIZE]; 
            bufferPointer = bytesRead = 0; 
        }
public String readLine() throws IOException 
        { 
            byte[] buf = new byte[64]; // line length 
            int cnt = 0, c; 
            while ((c = read()) != -1) 
            { 
                if (c == '\n') 
                    break; 
                buf[cnt++] = (byte) c; 
            } 
            return new String(buf, 0, cnt); 
        }
public int nextInt() throws IOException 
        { 
            int ret = 0; 
            byte c = read(); 
            while (c <= ' ') 
                c = read(); 
            boolean neg = (c == '-'); 
            if (neg) 
                c = read(); 
            do
            { 
                ret = ret * 10 + c - '0'; 
            }  while ((c = read()) >= '0' && c <= '9');
if (neg) 
                return -ret; 
            return ret; 
        }
public long nextLong() throws IOException 
        { 
            long ret = 0; 
            byte c = read(); 
            while (c <= ' ') 
                c = read(); 
            boolean neg = (c == '-'); 
            if (neg) 
                c = read(); 
            do { 
                ret = ret * 10 + c - '0'; 
            } 
            while ((c = read()) >= '0' && c <= '9'); 
            if (neg) 
                return -ret; 
            return ret; 
        }
public double nextDouble() throws IOException 
        { 
            double ret = 0, div = 1; 
            byte c = read(); 
            while (c <= ' ') 
                c = read(); 
            boolean neg = (c == '-'); 
            if (neg) 
                c = read();
do { 
                ret = ret * 10 + c - '0'; 
            } 
            while ((c = read()) >= '0' && c <= '9');
if (c == '.') 
            { 
                while ((c = read()) >= '0' && c <= '9') 
                { 
                    ret += (c - '0') / (div *= 10); 
                } 
            }
if (neg) 
                return -ret; 
            return ret; 
        }
private void fillBuffer() throws IOException 
        { 
            bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE); 
            if (bytesRead == -1) 
                buffer[0] = -1; 
        }
private byte read() throws IOException 
        { 
            if (bufferPointer == bytesRead) 
                fillBuffer(); 
            return buffer[bufferPointer++]; 
        }
public void close() throws IOException 
        { 
            if (din == null) 
                return; 
            din.close(); 
        } 
    } 
    static Reader sc=new Reader();
    static int MAX=100000;
 
    static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));

    static int MAX_SIZE = 1000005;

    static ArrayList<Integer> primes =
       new ArrayList<Integer>();
     

    static void SieveOfEratosthenes() 
    { 
        boolean [] IsPrime = new boolean[MAX_SIZE]; 
         
        for(int i = 0; i < MAX_SIZE; i++)
            IsPrime[i] = true;
         
        for (int p = 2; p * p < MAX_SIZE; p++) 
        { 

            if (IsPrime[p] == true) 
            { 
       
                for (int i = p * p; i < MAX_SIZE; i += p) 
                    IsPrime[i] = false; 
            } 
        } 

        for (int p = 2; p < MAX_SIZE; p++) 
        if (IsPrime[p] == true) 
                primes.add(p);
    } 
    //static ArrayList<Integer> b=new ArrayList<>();
   
   static void reverse1(int left,int right) {
	   while (left < right) {
           int temp = A[left];
           A[left++] = A[right];
           A[right--] = temp;
       }
 
   }
    static int[] A=new int[105];
    public static void main(String args[])throws IOException
    {
        
        		//SieveOfEratosthenes();
    			Scanner pp=new Scanner(System.in);
    	
    	
        	    int t=pp.nextInt();
        	   
        	    //int jj=1;
        	    while(t--!=0)
        	    {
        	    	
        	    	int a,b,c;
        	        a=pp.nextInt();
        	        b=pp.nextInt();
        	        c=pp.nextInt();
        	        long x = GetPower(10, a - 1);
        		
        			long y = GetPower(10, b - 1) + GetPower(10, c - 1);
        	     
        	       println(x+" "+y+"");
        	        
        	        
        	    }
    
        	    	 
	        	        
        	    

        	pp.close();
    	
        bw.flush();
        bw.close();
    }
    public static long GetPower(long  base, long  exponent) {
		int res = 1;
		while (exponent > 0) {
			if (((int)exponent & 1)!=0) {
				res *= base;
			}
			base *= base;
			exponent /= 2;
		}
		return res;
	}
    public static int[] swap(int data[], int left, int right)
    {
  
        // Swap the data
        int temp = data[left];
        data[left] = data[right];
        data[right] = temp;
  

        return data;
    }
  

    public static int[] reverse(int data[], int left, int right)
    {
  

        while (left < right) {
            int temp = data[left];
            data[left++] = data[right];
            data[right--] = temp;
        }
  

        return data;
    }
  

    public static boolean next_permutation(int data[])
    {
  

        if (data.length <= 1)
            return false;
  
        int last = data.length - 2;

        while (last >= 0) {
            if (data[last] < data[last + 1]) {
                break;
            }
            last--;
        }
  
 
        if (last < 0)
            return false;
  
        int nextGreater = data.length - 1;
  
        // Find the rightmost successor to the pivot
        for (int i = data.length - 1; i > last; i--) {
            if (data[i] > data[last]) {
                nextGreater = i;
                break;
            }
        }
  
        // Swap the successor and the pivot
        data = swap(data, nextGreater, last);
  
        // Reverse the suffix
        data = reverse(data, last + 1, data.length - 1);
  
        // Return true as the next_permutation is done
        return true;
    }

private static boolean count(int arr[],int n)
{
	int x=arr[0];
	int cnt=1;
	for(int i=1;i<n;i++)
	{
		if(arr[i]==x) cnt++;
	}
	if(cnt==n) return true;
	return false;

	
}
    private static boolean hasOddDivisor(long n) {
        long power2 = 2;
        while (power2 <= n) {
            if (n == power2)
                return false;
            power2 = power2 * 2;
        }

        return true;
    }
    static long abs(long a){
        return a>0 ? a:-a;
    }
    static boolean cal(int u, int r, int d, int l, int n)
    {
    	if((u<=n-1)&&(r<=n-1)&&(d<=n-1)&&(l<=n-1))
    		return true;
    	if(u==n)
    	{
    		if((r-1<=n-2)&&(l-1<=n-2)&&(d<=n-2))
    			return true;
    		else if(r-1==n-1)
    		{
    			if(d-1<=n-2)
    			{
    				if(l-1<=n-1)
    					return true;
    				else
    					return false; 
    			}
    			else if(d-1==n-1)
    			{
    				if(l-2<=n-2)
    					return true;
    				else 
    					return false;
    			}
    		}
    	}
    	return false;
     
    }
  
  

 
 public static boolean isPrime(int n) 
{
     
    // Check if number is less than 
    // equal to 1
    if (n <= 1) 
        return false; 
         
    // Check if number is 2 
    else if (n == 2) 
        return true;
         
    // Check if n is a multiple of 2
    else if (n % 2 == 0)
        return false;
         
    // If not, then just check the odds
    for(int i = 3; i <= Math.sqrt(n); i += 2) 
    {
        if (n % i == 0)
            return false;
    }
    return true;
}
    public static int inputInt()throws IOException
    {
        return sc.nextInt();
    }
    public static long inputLong()throws IOException
    {
        return sc.nextLong();
    }
    public static double inputDouble()throws IOException
    {
        return sc.nextDouble();
    }
    public static String inputString()throws IOException
    {
        return sc.readLine();
    }
    public static void print(String a)throws IOException
    {
        bw.write(a);
    }
    public static void printSp(String a)throws IOException
    {
        bw.write(a+" ");
    }
    public static void println(String a)throws IOException
    {
        bw.write(a+"\n");
    }
}
class Pair implements Comparable<Pair> {

    public int x;
    public int y;

    public Pair(int x, int y) {
        this.x = x;
        this.y = y;
    }


    @Override
    public String toString() {
        return (x + " " + y);
    }

    @Override
    public boolean equals(Object o) {
        if (!(o instanceof Pair)) return false;
        Pair pairo = (Pair) o;
        return this.x == pairo.x &&
                this.y == pairo.y;
    }
//Arrays.sort(pairArray,new Comparator<Pair>()
//
//    {
//        @Override
//        public int compare (Pair p1, Pair p2){
//        return p1.getL().compareTo(p2.getL());
//    }
//    });

    @Override
    public int compareTo(Pair p) {
        return Integer.compare(this.x, p.x);
    }
}
class SegmentTree { // Implemented to store min in a range , point update and range query
    int tree[];
    int len;
    int size;

    SegmentTree(int len) { // arr should be a 1 based array
        this.len = len;
        size = 1 << (32 - Integer.numberOfLeadingZeros(len - 1) + 1);  // ceil(log(len)) + 1
        tree = new int[size];
        Arrays.fill(tree, Integer.MAX_VALUE);
    }

    void update(int node, int idx, int val, int nl, int nr) {
        if (nl == nr && nl == idx)
            tree[node] = val;
        else {
            int mid = (nl + nr) >> 1;
            if (idx <= mid)
                update(2 * node, idx, val, nl, mid);
            else
                update((2 * node) + 1, idx, val, mid + 1, nr);

            tree[node] = Math.min(tree[2 * node], tree[(2 * node) + 1]);
        }
    }

    void update(int idx, int val) {
        update(1, idx, val, 0, len - 1);
    }

    int query(int L, int R) {
        if (L > R) return Integer.MAX_VALUE;
        return query(1, L, R, 0, len - 1);
    }

    int query(int node, int L, int R, int nl, int nr) {
        int mid = (nl + nr) >> 1;
        if (nl == L && nr == R)
            return tree[node];
        else if (R <= mid)
            return query(2 * node, L, R, nl, mid);
        else if (L > mid)
            return query((2 * node) + 1, L, R, mid + 1, nr);
        else
            return Math.min(query(2 * node, L, mid, nl, mid), query((2 * node) + 1, mid + 1, R, mid + 1, nr));
    }
}

class Maths {
    public final long MOD = (long) 1e9 + 7;
    public long[] fact = generateFactorials(1000000);
    public long[] invFact = generateReverseFactorials(1000000);

    public static long modInverse(long a, long m) {
        return power(a, m - 2, m);
    }

    public static long gcd(long a, long b) {
        if (a == 0)
            return b;
        return gcd(b % a, a);
    }

    public static long power(long a, long k, long m) {
        long res = 1;
        while (k > 0) {
            if ((k & 1) != 0) {
                res = res * a % m;
            }
            a = a * a % m;
            k >>= 1;
        }
        return res;
    }

    public long comb(final int m, final int n) {
        return (((fact[n] * invFact[m]) % MOD) * invFact[n - m]) % MOD;
    }

    public long[] generateFactorials(int count) {
        long[] result = new long[count];
        result[0] = 1;
        for (int i = 1; i < count; i++) {
            result[i] = (result[i - 1] * i) % MOD;
        }
        return result;
    }

    long[] generateReverseFactorials(int upTo) {
        final long[] reverseFactorials = new long[upTo];
        reverseFactorials[0] = reverseFactorials[1] = 1;
        final BigInteger BIG_MOD = BigInteger.valueOf(MOD);
        for (int i = 1; i < upTo; i++) {
            reverseFactorials[i] = (BigInteger.valueOf(i).modInverse(BIG_MOD).longValue() * reverseFactorials[i - 1]) % MOD;
        }
        return reverseFactorials;
    }
}
class Node {
    List<Integer> neighbors;

    Node() {
        neighbors = new ArrayList<>();
    }

    void addEdge(Integer v) {
        neighbors.add(v);
    }

    public List<Integer> getNeighbors() {
        return neighbors;
    }
}
class Graph {
    List<Node> nodes = new ArrayList<>();

    public Graph(int n) {
        for (int i = 0; i < n; ++i) {
            nodes.add(new Node());
        }
    }

    public Node getNode(int v) {
        return nodes.get(v);
    }

    public void addEdge(int u, int v) {
        getNode(u).addEdge(v);
        getNode(v).addEdge(u);
    }
}