C~K的难题

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

众所周知 C~K 喜欢数学,但是他最近被一个题给难住了,题目是这样的。
要求 (A/B)%10007,但由于 A 很大,我们只给出 n (n = A%10007)(我们给定的A必能被B整除,且 gcd(B,10007) = 1)。
你能帮助他解答吗?他会很感谢你的。

Input

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

Output

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

Sample Input

2
1000 53
87 123456789

Sample Output

8893
7424

Hint

Source

【山东理工大学第一届ACM知识挑战赛(机试)】C~K