Description

    要求(A/B)%9973，但由于A很大，我们只给出n(n=A%9973)(我们给定的A必能被B整除，且gcd(B,9973) = 1)。

Input

    数据的第一行是一个T，表示有T组数据。 
    每组数据有两个数n(0 <= n < 9973)和B(1 <= B <= 10^9)。

Output

    对应每组数据输出(A/B)%9973。

Sample Input

    2
    1000 53
    87 123456789

Sample Output

    7922
    6060 

题意：这道题是扩展欧几德里算法的简单应用，但这道题明明枚举就过了阿，不多说，上代码
ac代码：

///@zhangxiaoyu
///2015/8/13

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
typedef long long LL;

int main()
{
    int tt;
    scanf("%d",&tt);
    while(tt--)
    {
        LL n,b,i;
        scanf("%lld%lld",&n,&b);
        for(i=1;i<9973;i++)
        {
            if((b*i-n)%9973==0)
                break;
        }
        printf("%d\n",i);
    }
    return 0;
}