#include <bits/stdc++.h>
# define clr(x,a)        memset(x,a,sizeof(x))
# define all(a)          a.begin(), a.end()
# define deb(x)          cout<<#x<<"=="<<x<<endl;
# define deb2(x, y)      cout<<"("<<#x<<", "<<#y<<")==("<<x<<", "<<y<<")\n";
# define pb              push_back
# define sc              scanf
# define pr              printf
# define x               first
# define y               second
# define tc              int t; cin>>t; while(t--)
# define rev(s)          reverse(s.begin(),s.end())
# define linija          cout<<"___________\n";
# define FOR(i,j,k)      for(int i = j; i <= k; i++)
# define mp              make_pair

using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;

const int mxN=1000005, mxM=5005, LOG=25, inf = 2e9;
const long long mod=998244353;
const int MAX_Q = 349999;
int number;

pair<int, int> best_rational_approximation() {
    int a = 0, b = 1, c = 1, d = 1;

    while (b + d <= MAX_Q) {
        double mediant = (double)(a + c) / (b + d);
        int part = round(1000000 * mediant);

        if (part - number == 0) { // Allow slight rounding error
            return {a + c, b + d};  // Take mediant if within error range
        }

        if (part < number) {
            a += c;
            b += d;
        } else {
            c += a;
            d += b;
        }
    }

    return (b > d) ? make_pair(a, b) : make_pair(c, d);
}

pii res;
pii niz[mxN];
bool flag[mxN];


mt19937 rng_mt(chrono::steady_clock::now().time_since_epoch().count());

int rng(int l, int r) {
    uniform_int_distribution<int> dist(l, r);
    return dist(rng_mt);
}

int main() {
   cout << setprecision(8) << fixed;
   freopen("fantasy.in", "r", stdin);
   freopen("fantasy.out", "w", stdout);

    int Q;
    cin >> Q;
    number = 100001;
    while (Q--) {
         sc("%d", &number);
         //number = rng(1, 999999);
         if(number <= 99999){
            cout << number << " " << 1000000 << endl;
            continue;
         }

         while(number < 100000) number *= 10;

         if(flag[number]){
            res = niz[number];
         }
         else{
            res = best_rational_approximation();
            niz[number] = res;
         }

         flag[number] = 1;
         niz[number] = res;
        pr("%d %d\n", res.x, res.y);

        //cout << number << " " << 1.0*res.x/res.y << endl;
        number++;
    }

    return 0;
}