#include<bits/stdc++.h>

using  namespace std;
using ll = long long;
ll dd;
void exgcd(ll a,ll b,ll &x,ll &y){
    if(b == 0){
        x = 1;
        y = 0;
        dd = a;
        return ;
    }
    exgcd(b,a % b,y,x);
    y -= a / b * x;
}
map<ll,int> mp;
ll dfs_mod;
// (ad + bc) / bd (b * y + x * dfs_mod) == obj
ll ans = 1e18,ansd = -1;
ll a,b;
void dfs(ll nowd){
    if(mp.count(nowd))return ;
    if(nowd > 1e9) return ;
    mp[nowd] = 1;
    ll obj =(((- a * nowd) % dfs_mod) + dfs_mod) % dfs_mod;
    ll x,y;
    exgcd(b,dfs_mod,x,y);
    if(obj % dd == 0){
        ll k = obj / dd;
        ll res = ((k * x % dfs_mod) + dfs_mod) % dfs_mod;
        if(res < ans){
            ans = res;
            ansd = nowd;
        }
        // cout << dfs_mod << ' ' << k << ' ' << nowd << ' ' << res << ' ' << obj << '\n';
    }
    dfs(nowd * 2);
    dfs(nowd * 5);
}
void solve(){
    cin >> a >> b;
    vector<ll> facs;
    ans = 1e18;
    mp.clear();
    for(int i = 1;i * i <= b;i ++){
        if(b % i == 0){
            if(i % 2 != 0 && i % 5 != 0){
                facs.push_back(i);
            }
            int inv = b / i;
            if(inv != i && inv % 2 != 0 && inv % 5 != 0){
                facs.push_back(inv);
            }
        }
    }
    ll val = b;
    while(val % 2 == 0)val /= 2;
    while(val % 5 == 0) val /= 5;
    for(auto fac : facs){
        dfs_mod = val * fac;
        dfs(fac);
    }
    cout << ans << ' ' << ansd << '\n';
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    cin >> t;
    while(t --){
        solve();
    }
}