#ifndef rtgsp
#include "hack.h"
#endif // rtgsp
#include<bits/stdc++.h>
#define ll long long
#define task ""
using namespace std;
const int maxn = 1e6 + 4;
int t, n, x, op = 0;
vector<ll> v;
map<int, int> mp;
#ifdef rtgsp
ll collisions (vector<ll> x)
{
op += x.size();
ll res = 0;
mp.clear();
for (ll i : x)
res += mp[i % n]++;
return res;
}
#endif // rtgsp
int hack ()
{
int l = 5e8 + 1, r = 1e9, m = 0;
op = 0;
while (l < r)
{
m = (l + r)/2;
x = sqrt(m - l + 1);
v.clear();
for (int i = 1; i <= x; i++) v.push_back(i);
for (int i = l + x; i <= m + x; i += x) v.push_back(min(i, m + 1));
if (collisions(v)) r = m;
else l = m + 1;
}
m = sqrt(r);
for (int i = 2; i <= m; i++)
{
if (r % i == 0)
{
while (r % i == 0) r /= i;
while (l % i == 0 && collisions({1, l/i + 1})) l /= i;
}
}
if (r > 1 && l % r == 0 && collisions({1, l/r + 1})) l /= r;
return l;
}
#ifdef rtgsp
int main ()
{
//freopen(task".INP", "r", stdin);
//freopen(task".OUT", "w", stdout);
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> t;
while (t--)
{
cin >> n;
cout << hack() << " " << op << endl;
}
}
#endif // rtgsp
