#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
template <typename T> using min_heap = priority_queue<T, vector<T>, greater<T>>;

/******* MISC ********/
void print128(__int128 n) {
	if (n == 0) {
		cout << "0\n";
		return;
	}
	if (n < 0) {
		cout << "-";
		n *= -1;
	}
	string ans;
	while (n) {
		ans.push_back('0' + n%10);
		n /= 10;
	}
	reverse(ans.begin(), ans.end());
	cout << ans << '\n';
}

/******* MATH ********/
typedef unsigned long long ull;
ull modmul(ull a, ull b, ull M) {
	ll ret = a * b - M * ull(1.L / M * a * b);
	return ret + M * (ret < 0) - M * (ret >= (ll)M);
}
ull modpow(ull b, ull e, ull mod) {
	ull ans = 1;
	for (; e; b = modmul(b, b, mod), e /= 2)
		if (e & 1) ans = modmul(ans, b, mod);
	return ans;
}

/******* POLLARD RHO ********/
bool isPrime(ull n) {
	if (n < 2 || n % 6 % 4 != 1) return (n | 1) == 3;
	ull A[] = {2, 325, 9375, 28178, 450775, 9780504, 1795265022},
		s = __builtin_ctzll(n-1), d = n >> s;
	for (ull a : A) {   // ^ count trailing zeroes
		ull p = modpow(a%n, d, n), i = s;
		while (p != 1 && p != n - 1 && a % n && i--)
			p = modmul(p, p, n);
		if (p != n-1 && i != s) return 0;
	}
	return 1;
}
ull pollard(ull n) {
	ull x = 0, y = 0, t = 30, prd = 2, i = 1, q;
	auto f = [&](ull x) { return modmul(x, x, n) + i; };
	while (t++ % 40 || __gcd(prd, n) == 1) {
		if (x == y) x = ++i, y = f(x);
		if ((q = modmul(prd, max(x,y) - min(x,y), n))) prd = q;
		x = f(x), y = f(f(y));
	}
	return __gcd(prd, n);
}
vector<ull> factor(ull n) {
	if (n == 1) return {};
	if (isPrime(n)) return {n};
	ull x = pollard(n);
	auto l = factor(x), r = factor(n / x);
	l.insert(l.end(), all(r));
	return l;
}

/******* FIBONACCI TEST ********/

typedef vector<ll> Poly;
ll linearRec(Poly S, Poly tr, ll k, ll mod) {
	int n = sz(tr);

	auto combine = [&](Poly a, Poly b) {
		Poly res(n * 2 + 1);
		rep(i,0,n+1) rep(j,0,n+1)
			res[i + j] = (res[i+j] + modmul(a[i], b[j], mod)) % mod;
		for (int i = 2 * n; i > n; --i) rep(j,0,n)
			res[i - 1 - j] = (res[i - 1 - j] + modmul(res[i], tr[j], mod)) % mod;
		res.resize(n + 1);
		return res;
	};

	Poly pol(n + 1), e(pol);
	pol[0] = e[1] = 1;

	for (++k; k; k /= 2) {
		if (k % 2) pol = combine(pol, e);
		e = combine(e, e);
	}

	ll res = 0;
	rep(i,0,n) res = (res + modmul(pol[i + 1], S[i], mod)) % mod;
	return res;
}

ll fibmod(ll n, ll m) {
    return linearRec({0, 1}, {1, 1}, n+1, m);
}

// is p a valid period of modulo m?
mt19937 rng(time(NULL));
const int TEST_CNT = 10;
bool isPeriodic(ll m, ll p) {
    rep(i,0,TEST_CNT) {
        ll g = abs((int)rng()) % p;
        if (fibmod(g, m) != fibmod(g+p, m)) return 0;
		if (fibmod(g, m) != fibmod(g+2*p, m)) return 0;
		if (fibmod(g, m) != fibmod(g+3*p, m)) return 0;
    }
    return 1;
}

/******* SOLUTION ********/

// pisano period of fibonacci mod p, p is prime
ll solvePrime(ll p) {
    if (p == 2) return 3;
    if (p == 3) return 8;
    if (p == 5) return 20;

    ll cand;
    if (p%5 == 1 || p%5 == 4) cand = p-1;
    else cand = 2*(p+1);

    // pisano period is any divisor of cand
    vector<ull> ft = factor(cand);
    ll ans = cand;
    
	for (ull i: ft) {
		if (isPeriodic(p, ans/i)) ans /= i;
	}
    return ans;
}

// pisano period of fibonacci mod p^q, p is prime
ll solvePrimePower(ll p, ll q) {
    ll kp = solvePrime(p);
    ll m = 1;
    rep(i,0,q) m *= p;

    // pisano period is a divisor of p^(q-1) * kp
    for (int i = 0; i <= q; i++) {
        if (isPeriodic(m, kp)) return kp;
        kp *= p;
    }
    return kp;
}

__int128 ggcd(__int128 a, __int128 b){ 
	while (a&&b)a>b?a%=b:b%=a; 
	return a+b; 
} 
 
__int128 llcm(__int128 a, __int128 b){ 
	return a/ggcd(a,b)*b; 
}

void solve() {
    string trash; cin >> trash;
    ll m; cin >> m;
    vector<ull> f = factor(m);
    map<ull, int> mp;
    for (ull i: f) mp[i]++;

    __int128 ans = 1;
    for (auto [p, q]: mp) {
        ans = llcm(ans, solvePrimePower(p, q));
    }
    cout << trash << ' ';
    print128(ans);
}

signed main() {
    ios::sync_with_stdio(0); cin.tie(0);

    int t = 1; cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}