时间限制：1秒　　内存限制：256M

---

【题目描述】

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

【输入格式】

　　数据的第一行是一个 \(T\)，表示有 \(T\) 组数据。每组数据有两个数 \(n\) 和 \(B\)。

【输出格式】

　　对应每组数据结果。

【输入输出样例】

　Input

2
1000 53
87 123456789

　Output

7922
6060

【数据限制】

　　对于 \(100\%\) 的数据，\(0≤n<9973\)，\(1≤B≤10^9\)。

【来源】

　　Mr.he