Migrated from Lutece 2664 Kanade Hates Modular Multiplicative Inverse

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

纯音乐，请您欣赏。

——《夏影》

在 2020，2021 年暑假前集训题中，出现了很多带有逆元的题，这对于没有经验的新人来说十分不友好。去年甚至出现了逆元出现在数据结构专题，但是讲逆元是在数学与几何专题的问题（当然今年也一样）。

但是有了逆元，出题人可以在不考虑精度影响的情况下较为准确地与选手输出比较，如果答案不同那结果是错的，如果答案相同可以保证选手答案大概率是对的，所以现在的最佳实践是在出现需要选手输出实数时，如果可以的话使用逆元。

总而言之 Kanade 还是不喜欢逆元这种表达方式，她更喜欢直接一点，比如用分数表达。有那么一道题的输出都是输出逆元，Kanade 觉得很不好，于是她想改成输出分数。

形式化地说，给定一个质数 $p$ 和一个正整数 $x$，Kanade 想知道一组正整数 $a,b$，满足：

• $a\equiv bx\pmod p$
• $b$ 最小，且在 $b$ 最小的情况下 $a<b$

Kanade 会问 $T$ 次类似的问题。

Input

第一行一个正整数 $T$，表示询问个数。

接下来 $T$ 行，每行两个正整数 $x,p$，意义如题目描述。

Output

输出 $T$ 行，表示对于每个询问的回答，每行输出形如 $a/b$ 形式的字符串，表示这个分数。

Samples

4
3 5
7 101
114514 998244853
1919810 100000007

1/2
4/15
9254/34869
869/5886

Constraints

$1\le T\le 2\times 10^5,3\le p\le 10^{15},1<x<p$，保证 $p$ 是一个质数。

Resources

2021 UESTC ICPC Training for Math and Geometry