#include <cstdio>

#include <iostream>

#include <string>

using namespace std;

typedef long long ll;

ll exgcd(ll a,ll b,ll &x,ll &y)

{

    if(b==)

    {

        x=;

        y=;

        return a;

    }

    ll temp=exgcd(b,a%b,y,x);

    y-=(a/b)*x;

    return temp;

}

int main()

{

    int t;

    cin>>t;

    while(t--)

    {

        ll n,b;

        cin>>n>>b;

        ll x,y;

        ll g=exgcd(b,,x,y);

        ll t=/g;// t为最小间距

        x=(x*(n/g)%t+t)%t;//  求解最小正整数解的过程

        cout<<x<<endl;

    }

    return ;

}