#include <iostream>
using namespace std;

using ll = long long;
constexpr ll INFll = (ll)1e18 + 1;

ll Power(int a, int b) {
    ll ret = 1;
    while(b--) {
        if(INFll / ret < a) {
            ret = INFll;
            break;
        }
        ret *= a;
    }

    return ret;
}

int main() {

    ll n; cin >> n;
    for(int i = 1; i < 100; ++i) {
        for(int j = 1; j < 100; ++j) {
            if(Power(3, i) + Power(5, j) == n) {
                cout << i << " " << j << endl;
                return 0;
            }
        }
    }

    cout << -1 << endl;

    return 0;
}
#include<bits/stdc++.h>
using namespace std;
void __print(int x){cout<<x;}void __print(long x){cout<<x;}
void __print(long long x){cout<<x;}void __print(unsigned x){cout<<x;}
void __print(unsigned long x){cout<<x;}void __print(unsigned long long x){cout<<x;}
void __print(float x){cout<<x;}void __print(double x){cout<<x;}
void __print(long double x){cout<<x;}void __print(char x){cout<<'\''<<x<<'\'';}
void __print(const char *x){cout<<'\"'<<x<<'\"';}void __print(const string &x){cout<<'\"'<<x<<'\"';}
void __print(bool x) {cout<<(x?"true":"false");}
template<typename T, typename V>
void __print(const pair<T, V> &x) {cout << '{'; __print(x.first); cout << ','; __print(x.second); cout << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cout << '{'; for (auto &i: x) cout << (f++ ? "," : ""), __print(i); cout << "}";}
void _print() {cout << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cout << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cout << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
           
#define lp(i,a,b)       for (int i=a;i<=b;i++)
#define rp(i,a,b)       for (int i=a;i>=b;i--)
#define ms(a,x)         memset(a,x,sizeof a)
#define ll              long long 
#define ff              first
#define ss              second
#define all(a)          a.begin(),a.end()
#define rall(a)         a.rbegin(),a.rend()
#define pb              push_back
#define nl              cout<<"\n"
#define gcd(a,b)        __gcd((a),(b))
#define lcm(a,b)        ((a)*(b))/(gcd(a,b))
#define sq(a)           ((a)*(a))
#define sz(a)           (int) a.size()
#define mod             1000000007
#define PI              (2*acos(0.0))

void solve()
{
  int n;
  cin>>n;
  int cnt=3;
  while(cnt--)
  {
    string s;
    cin>>s;
  }
  cout<<string(n,'1')+string(n,'0')+'1';
  nl;
}
int main()
{
  ios_base::sync_with_stdio(false); 
  cin.tie(NULL); cout.tie(NULL);
  int T=1;
  cin>>T;
  while(T--) solve();
  return 0;
}
