Mr. Panda 和 Mr. Sheep 想要入侵一款著名手游的系统。他们已经导出了资源代码，并截获了该加密伪代码输出的加密信息 $n$ 和 $c$。

1: function GetKakinEntryPoint(FLAG)
2: x ← a uniformly random integer in range [10^5, 10^9]
3: p ← the largest prime less than x
4: q ← the smallest prime not less than x
5: n ← p · q
6: c ← FLAG^(2^30+3) mod n

最重要的是变量 FLAG。如果他们得到了它的值，就能获得这款手游中作为通用货币的无限魔法石。这就是他们来找你这位密码学大师的原因。你需要帮助他们求出 FLAG 的值，更准确地说，是 FLAG 除以 $n$ 的余数。

输入格式

第一行输入包含测试用例的数量 $T$ ($1 \le T \le 10^5$)。接下来是 $T$ 个测试用例。 每个测试用例包含两个整数 $n$ 和 $c$ ($10^{10} \le n \le 10^{18}$, $0 < c < n$)，表示加密代码的输出。保证这些数字是有效的，且仅对应一个 FLAG 值。

输出格式

对于每个测试用例，输出 “Case x: y”，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是 FLAG 的值。

样例

输入 1

3
181857896263 167005790444
218128229323 156323229335
352308724847 218566715941

输出 1

Case 1: 175267324024
Case 2: 209603568635
Case 3: 282077284785