#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==0)
    {
        x=1;
        y=0;
        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,9973,x,y);
        ll t=9973/g;// t为最小间距
        x=(x*(n/g)%t+t)%t;//  求解最小正整数解的过程
        cout<<x<<endl;
    }
    return 0;
}