#include <bits/stdc++.h>
using namespace std;
const int inf = 1e12;
long long exgcd(long long a,long long b,long long &x,long long &y)
{
    if(!b)
    {
        x = 1,y = 0;
        return a;
    }
    else
    {
        long long g = exgcd(b,a % b,y,x);
        y -= a / b * x;
        return g;
    }
}



void solve()
{
    long long a,b;
    cin>>a>>b;
    long long w = 1;
    long long p = b;
    while(p % 2 == 0)
        p /= 2,w *= 2;
    while(p % 5 == 0)
        p /= 5,w *= 5;
    if(p == 1){
        cout<<0<<"\n";
        return;
    }
    long long x,y;
    long long g = exgcd(p,a,x,y);
    long long c = g;
    long long d = c / g;
    //x大于等于0的最小解，在这基础上x + b/g,y - a/g为一个新解
    x = ((__int128)(x * d) % (a / g) + a / g) % (a / g);
    y = (c - p * x) / a;
    if(y >= 0){
        long long k = y / (p / g);
        y -= k * (p / g);
        x += k * (a / g);
        if(y >= 0){
            y -= p / g;
            x += a / g;
        }
    }
    y = -y;
    // cout<<p<<" "<<x<<" "<<a<<" "<<y<<" "<<p / g<<" "<<a / g<<"\n";
    // cout<<3 * g<<" "<<b * (-y)<<"\n";
    long long ans = 1e12,bot = 0;
    for(long long i = 1;b * i <= inf;i *= 5){
        for(long long j = 1;b * i * j <= inf;j *= 2){
            long long cc = i * j;

            long long aa = y,bb = p / g;
            long long xx,yy;
            long long gg = exgcd(aa,bb,xx,yy);
            //y + k * p / g = cc
            if(cc % gg != 0)
                continue;
            long long dd = cc / gg;
            xx = ((__int128)(xx * dd) % (bb / gg) + bb / gg) % (bb / gg);
            yy = (cc - aa * xx) / bb;
            long long ansc = (xx * x + (a / g) * yy) * p - cc * a;
            long long rg = __gcd(ansc,b * cc);
            if(b * cc / rg <= 1e9 && ansc / rg < ans){
                ans = ansc / rg;
                bot = b * cc / rg;
            }
        }
    }
    cout<<ans<<"\n";

}
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int T;
    std::cin >> T;
    
    while (T--) {
        solve();
    }
    
    return 0;
}