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

Solution:
#include<bits/stdc++.h>
using namespace std;

#define ff              first
#define ss              second
#define int             long long
#define pb              push_back
#define mp              make_pair
#define fi(n)           for(int i=0;i<n;i++)
#define fj(n)           for(int j=0;j<n;j++)
#define pii             pair<int,int>
#define vi              vector<int>
#define vvi             vector<vi>
#define mii             map<int,int>
#define pqb             priority_queue<int>
#define pqs             priority_queue<int,vi,greater<int> >
#define inf             1e18
#define deb(x)          cout << #x << "=" << x << '\n';
#define ps(x,y)         fixed<<setprecision(y)<<x
#define FIO             ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
const char ln='\n';
const char sp=' ';
const int mod=1000000007;
int modpow(int x, int y, int p);
int modinv(int a, int m);
int lcm(int a, int b);
int gcd(int a, int b);
bool po2 (int x);
struct comp;
bool isPrime(int n)
{
    if (n <= 1)  return false;
    if (n <= 3)  return true;
    if (n%2 == 0 || n%3 == 0) return false;
    for (int i=5; i*i<=n; i=i+6)
        if (n%i == 0 || n%(i+2) == 0)
           return false;
    return true;
}

int nextPrime(int N)
{
    if (N <= 1)
        return 2;
    int prime = N;
    bool found = false;
    while (!found) {
        prime++;
 
        if (isPrime(prime))
            found = true;
    }
 
    return prime;
}
 

void solve(){
    int a,b,c;
    cin >> a >> b >> c;
    if(a!=b){
        a = nextPrime(pow(10,a-c));
        b = nextPrime(pow(10,b-c));
    }else{
        a = nextPrime(pow(10,a-c));
        b = nextPrime(a);
    }
    c = nextPrime(pow(10,c-1));
    cout << a*c << sp << b*c << ln;
    // cout << gcd( a*c ,b*c)<< ln;
}

int32_t main() {
    FIO;
    int t = 1;
    cin >> t;
    while(t--) {
        solve();
    }
    return 0;
}

int gcd(int a, int b) {
    if (a == 0) return b;
    return gcd(b % a, a);
}

int lcm(int a, int b) {
    return (a * b) / gcd(a, b);
}

bool po2(int x) {
    return x && (!(x&(x-1)));
}

int modpow(int x, int y, int p) {
    int res = 1;
    x = x % p;
    if (x == 0)
        return 0;
    while (y > 0) {
        if (y & 1)
            res = (res * x) % p;
        y = y >> 1;
        x = (x * x) % p;
    }
    return res;
}

int modinv(int a, int m) {
    int g = gcd(a, m);
    if (g != 1)
        return -1;
    else {
        return modpow(a, m - 2, m);
    }
}

struct comp {
    bool operator()(pii const& p1, pii const& p2) {
        if(p1.first>p2.first) return true;
        else if(p1.first<p2.first) return false;
        else return p1.second>p2.second;
    }
};