J20 习题-5 A/B

题目描述

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

输入格式

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

输出格式

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

样例输入

2
1000 53
87 123456789

样例输出

7922
6060

样例分析

如上所述。

数据范围

对于 $100\%$ 的数据：$0 \le n \lt 9973$，$1 \le B \le 10^9$。