#include<bits/stdc++.h>
using namespace std;
#define int long long
#define gcd __gcd
const int maxd=1E9;

// 扩展欧几里得算法，用于求 x 和 y，使 ax + by = gcd(a, b)
void extendedEuclid(int a, int b, int &x, int &y, int &g) {
    if (b == 0) {
        x = 1;
        y = 0;
        g = a;
        return;
    }
    int x1, y1;
    extendedEuclid(b, a % b, x1, y1, g);
    x = y1;
    y = x1 - (a / b) * y1;
}

// 找到最小正整数 c
int findMinC(int a, int x, int k) {
    a = ((-a % k) + k) % k; // 将 -a 调整到 [0, k) 范围
    int invX, tempY, gcd;
    extendedEuclid(x, k, invX, tempY, gcd); // 计算 x 和 k 的最大公约数及模逆

    // 检查是否有解
    if (a % gcd != 0) {
        return -1;
    }

    // 计算基本解
    invX = (invX % k + k) % k; // 确保 invX 是非负的
    int c = (invX * (a / gcd)) % k;

    if (c < 0) c += k; // 确保 c 是非负的
    return c;
}


void solve()
{
    int a,b,c=1E18,d=0,c1=0,c2=0;
    scanf("%lld %lld",&a,&b);
    int k=b;
    while(k%2==0){k=k/2;c1++;}
    while(k%5==0){k=k/5;c2++;}
    if(k==1)
    {
        printf("0 1\n");return;
    }
    map<int,int> mp;
    priority_queue<int,vector<int>,greater<int>> pq;
    mp[b]=1;
    pq.push(b);
    while(!pq.empty())
    {
        int x=pq.top();pq.pop();
        if(5*x<=maxd&&!mp[5*x])
        {
            mp[5*x]=1;
            pq.push(5*x);
        }
        if(2*x<=maxd&&!mp[2*x])
        {
            mp[2*x]=1;
            pq.push(2*x);
        }
        int res=findMinC(a*x/b,1,k);
        int m=gcd(res,x);
        res=res/m;x=x/m;
        if(res>0){
            
            if(res<c){c=res;d=x;}
        }
    }


    for(int i=0;i<=c1;i++)
    {
        for(int j=0;j<=c2;j++)
        {
            int x=k*pow(2,i)*pow(5,j);
            int y=b/x;
            // a/b+c/x  y=b/x
            // a = k*m-c*y
            int res=findMinC(a,y,k);
            //printf("!%d\n",res);
            int m=gcd(res,x);
            res=res/m;x=x/m;
            if(res>0&&c>res)
            {
                c=res;
                d=x;
            }
        }
    }

    printf("%lld %lld\n",c,d);
}

signed main()
{
    int tt;
    scanf("%lld",&tt);
    while(tt--)
    {
        solve();
    }
}