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 <iostream>
#include <bits/stdc++.h>

using namespace std;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define ll long long
#define forn(i,a,n,b) for(ll i=a;i<n;i+=b)
#define forr(i,a,n,b) for(ll i=a;i>=n;i-=b)
#define MOD 1000000007

#define vll vector<ll>
#define vb vector<bool>
#define vpll vector<pair<ll, ll>>
#define vvll vector<vector<ll>>

#define mem(arr, value) memset(arr, value, sizeof(arr))
#define mp(val1, val2) make_pair(val1, val2)
#define endn "\n"
#define ff first
#define ss second

// DEBUG
void __print(int x) { cerr << x; }
void __print(ll x) { cerr << x; }
void __print(double x) { cerr << x; }
void __print(char x) { cerr << '\'' << x << '\''; }
void __print(const char* x) { cerr << '\"' << x << '\"'; }
void __print(const string& x) { cerr << '\"' << x << '\"'; }
void __print(bool x) { cerr << (x ? "true" : "false"); }

template<typename T, typename V>
void __print(const pair<T, V>& x) { cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}'; }
template<typename T>
void __print(const T& x) { int _ = 0; cerr << '{'; for (auto& i : x) cerr << (_++ ? "," : ""), __print(i); cerr << "}"; }
void _print() { cerr << "]\n"; }
template <typename T, typename... V>
void _print(T t, V... v) { __print(t); if (sizeof...(v)) cerr << ", "; _print(v...); }
#ifndef ONLINE_JUDGE
#define dbg(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define dbg(x...)
#endif
vll fact(100001);

bool compare(ll a, ll b)
{
    return a>b;
}


ll gcd(ll a, ll b) {if (b > a) {return gcd(b, a);} if (b == 0) {return a;} return gcd(b, a % b);}
ll fastexpo(ll a, ll b, ll mod) {ll res = 1; while (b > 0) {if (b & 1)res = (res * a) % mod; a = (a * a) % mod; b = b >> 1;} return res;}
void extendgcd(ll a, ll b, vll &v) {if (b == 0) {v[0] = 1; v[1] = 0; v[2] = a; return ;} extendgcd(b, a % b, v); ll x = v[1]; v[1] = v[0] - v[1] * (a / b); v[0] = x; return;}

ll modulo_inv(ll a, ll b) {vll arr(3); extendgcd(a, b, arr); return arr[0];} //for non prime b
ll modulo_inv_prime(ll a, ll b) {return fastexpo(a, b - 2, b);}


ll ncr(ll n, ll r)
{
    if (n < r)
    {
        return 0;
    }
    ll ans = fact[n];
    ans = ( ans * modulo_inv_prime(fact[r], MOD) ) % MOD;
    ans = ( ans * modulo_inv_prime(fact[n-r], MOD)%MOD) % MOD;
    return ans;
}

void solve()
{
    ll a, b, c;
    cin >> a >> b >> c;
    string x, y;
    x += "1";
    forn(i,1,a,1)
    {
        x += "0";
    }
    forn(i,0,b-c+1,1)
    {
        y += "1";
    }
    forn(i,0,c-1,1)
    {
        y += "0";
    }
    cout << x << " "<< y << "\n";
}

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