#include<stdio.h>
int main()
{
    int T,n,i;
    long long int B;
    scanf("%d",&T);
    while(T--)
    {
    scanf("%d%lld",&n,&B);
     for(i=0;i<=10000;i++)
     if((B*i-n)%9973==0) break;
     printf("%d\n",i);    
    }
    return 0;
 }