#include<bits/stdc++.h>
#define int long long
#define double long double
#define x first
#define y second
using namespace std;
typedef long long LL;
typedef long long ll;
typedef pair<int,int> PII;
const int N=3e5+10;
const int M=1e3+10;
int mod=998244353;
vector<int>sp;
//exgcd可以求出不定方程 ax+by=c的一组特解
//原方程有解的条件是c%gcd(a,b)==0;
//即求 ax+by=gcd(a,b) 的一组特解，然后将x和y乘以 c/gcd(a,b) 即可
//1.当b等于0时，x=1,y=0即可
//2.当b!=0时，根据递归的x1,y1反解出上一层的x和y
//x=y1,y=(x1-a/b*y1),回溯的时候用.
//通解为 x=x1+s*dx,t=y1-s*dy; 其中dx=b/gcd(a,b),dy=a/gcd(a,b);
int gcd(int a,int b){
    if(b==0) return a;
    return gcd(b,a%b);
}
void Exgcd(int a,int b,int &x,int &y){
    if(!b){
        x=1,y=0;
        return ;
    }
    int p;
    Exgcd(b,a%b,x,y);
    p=x;
    x=y;
    y=p-a/b*y;
    return ;
}
int check(int x){
    if(x%5==0||x%2==0) return 1;
    return 0;
}
void solve(){
    int a,b;cin>>a>>b;
    int pp=1;
    for(int i=1;i*i<=b;i++){
        if(b%i==0){
            if(!check(i)) pp=max(pp,i);
            if(!check(b/i)) pp=max(pp,b/i);
        }
    }
    // if(pp==1){
        // cout<<0<<" "<<1<<"\n";
        // return ;
    // }
    int ansc=1e18;
    int ansd=1e18;
    for(auto u:sp){
        if(u*pp*b>1e18) break;
        int d=u*pp;
        int aa=pp*pp;
        int bb=-b;
        int cc=a*d;
        if(cc%__gcd(aa,bb)!=0) continue;
        int x0=0,y0=0;
        Exgcd(aa,bb,x0,y0);
        int g=cc/__gcd(aa,bb);
        int dx=bb/__gcd(aa,bb),dy=aa/__gcd(aa,bb);
        x0*=g,y0*=g;
        // if(u==1){
            // cout<<x0<<" "<<y0<<" "<<dx<<" "<<dy<<"\n";
        // }
        int s;
        if(dy<0) s=ceill(y0*1.0/dy);
        else s=floorl(y0*1.0/dy);
        y0-=s*dy;
        if(u==1) cout<<s<<"\n";
        if(x0+s*dx>=0){
            int cp=__gcd(y0,d);
            if(d/cp>1e9) continue;
            if(y0/cp<ansc) ansc=y0/cp,ansd=d/cp;
        }
    }
    cout<<ansc<<" "<<ansd<<"\n";
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr),cout.tie(nullptr);
    int _;
    for(int i=0;(int)powl(2,i)<=1000000000;i++){
        int x=(int)pow(2,i);
        for(int j=0;(int)powl(5,j)*x<=1000000000;j++){
            sp.push_back((int)powl(5,j)*x);
        }
    }
    sort(sp.begin(),sp.end());
    // cout<<sp[0]<<"\n";
    _=1;
    cin>>_;
    while(_--){
        solve();
    }
}