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

const int N = 1e5 + 10;

int num[N], cnt;

long long quik_power(int base, int power)
{
    long long result = 1;
    while (power > 0)
    {
        if (power & 1)
            result = result * base;
        base = base * base;
        power >>= 1;
    }
    return result;
}

int exgcd(int a,int b,int &x,int &y)
{
    if(!b){x = 1,y = 0;return a;}
    else 
    {
        int d = exgcd(b,a%b,x,y);
        int c = y;
        y = x-a/b*y;
        x = c;
        return d;
    }
}

void solve()
{
    int c = 0x3f3f3f3f3f3f3f3f;
    int a, b;
    cin >> a >> b;
    int p = b;
    int ansd = 0;
    while (p % 2 == 0)
        p /= 2;
    while (p% 5 == 0)
        p /= 5;
    if(p==1){
        cout << 0 << ' ' << 1 << endl;
        return;
    }
    for (int i = 1; i <= cnt; i++)
    {
        int d = num[i] * p;
        if (d > 1e9)
            break;
        int x,y,aq1;
        aq1 = a*num[i];
        exgcd(b/p,-p,x,y);
        x = -aq1*x;
        //y = aq1*y;
        x = (x%p+p)%p;
        if(c>x)c = x,ansd = d;
    }
    cout << c << ' ' << ansd << endl;
}

signed main()
{
    int tt = 1;
    cin >> tt;
    for (int i = 0; i <= 29; i++)
    {
        for (int j = 0; j <= 12; j++)
        {
            int cc = quik_power(2, i) * quik_power(5, j);
            if (cc <= 1e9)
            {
                num[++cnt] = cc;
            }
            else
                break;
        }
    }
    sort(num + 1, num + 1 + cnt);
    // cout << cnt << endl;
    while (tt--)
    {
        solve();
    }
}