#include<iostream>

#include<cstring>

#include<algorithm>

#include<queue>

#include<map>

#include<stack>

#include<cmath>

#include<vector>

#include<fstream>

#include<set>

#include<cstdio>

using namespace std;

#define eps 1e-8

typedef long long ll;

#define INF 0x3f3f3f3f

ll n,B,d,x,y;

int t;

void ex_gcd(ll a,ll b ,ll &d,ll &x,ll &y)

{

    if(!b)

    {

        d=a;

        x=;

        y=;

        return;

    }

    ex_gcd(b,a%b,d,y,x);

    y-=x*(a/b);

}

int main()

{

    cin>>t;

    while(t--)

    {

        cin>>n>>B;

        ex_gcd(B,,d,x,y);

        x*=n;    //这里d一定是1，因为gcd（B，9973）==1

        x%=;

        if(x<)    //在这里如果<变成<=也可以ac，但是我觉得不能加，否则应该会出现x=9973的情况

        x+=;

        cout<<x<<endl;

    }

    return ;

}