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>
  #define MOD 1000000007
  #define test int t; cin>>t; while(t--)
  #define init(arr,val) memset(arr,val,sizeof(arr))
  #define loop(i,a,b) for(int i=a;i<b;i++)
  #define loopr(i,a,b) for(int i=a;i>=b;i--)
  #define loops(i,a,b,step) for(int i=a;i<b;i+=step)
  #define looprs(i,a,b,step) for(int i=a;i>=b;i-=step)
  #define ull unsigned long long int
  // #define int long long int
  #define P pair
  #define PLL pair<long long, long long>
  #define PII pair<int, int>
  #define PUU pair<unsigned long long int, unsigned long long int>
  #define L list
  #define V vector
  #define D deque
  #define ST set
  #define MS multiset
  #define M map
  #define UM unordered_map
  #define mp make_pair
  #define pb push_back
  #define pf push_front
  #define MM multimap
  #define F first
  #define S second
  #define IT iterator
  #define RIT reverse_iterator
  #define FAST ios_base::sync_with_stdio(false);cin.tie();cout.tie();
  #define FILE_READ_IN freopen("input.txt","r",stdin);
  #define FILE_READ_OUT freopen("output.txt","w",stdout);
  #define all(a) a.begin(),a.end()
  #define ld long double
  using namespace std;
  // const ll maxn = 1e5;
  // const ll inf = 1e9;
  const double pi = acos(-1);
  // map<int,string>arr;
  void solve()
  {
    string prim[]={"3","5","13","17","103","107","1091","1093","15581","15601","155581","155593","1555607","1555613","15555569","15555587","155555591","155555597"};
    int a,b,c;
    cin>>a>>b>>c;
    int dp=2*(a-c);
    int da=2*(b-c);
    if(a==b){
      da++;
    }
    for(int i=0; i<c-1; i++)
    {
      prim[da]+="0";
      prim[dp]+="0";
    }
    cout<<prim[dp]<<" "<<prim[da]<<endl;
  }
  int32_t main(){
    int n=1;
    cin>>n;
    while(n--){
      solve();
    }
    return 0;
  }