#include <cstdio>

using namespace std;

#define max(a,b) (a>b?a:b)

#define min(a,b) (a<b?a:b)

#define mod 9973

using namespace std;

long long exc_gcd(long long a,long long b,long long &x,long long &y)

{

    if(!b)

    {

        x=,y=;

        return a;

    }

    long long g=exc_gcd(b,a%b,x,y);

    long long t=x;

    x=y;

    y=t-(a/b)*y;

    return g;

}

int main()

{

    int t,n;

    long long b;

    while(~scanf("%d",&t))

    {

        while(t--)

        {

            scanf("%d%I64d",&n,&b);

            long long x=,y=;

            long long b1=exc_gcd(b,mod,x,y);

            if(x<) x+=mod;

            long long ans=(n*(x%mod)+mod)%mod;

            printf("%I64d\n",ans);

        }

    }

    return ;

}