题目描述

今天无聊的 $cbh$ 发现了两个有趣的函数，分别命名为 $f(x)$ 与 $g(x)$ 。 但是 $cbh$ 觉得这两个函数的计算太简单了，所以对其又进行了改变，问题变为求解下面这个等式。 $f(x)^{l} \equiv g(n)$$(mod$ $p)$ ， 其中 $p$ 为一个质数。 $l$ 是你要求解的，如果存在解就输出最小的 $l$ ，不然就输出 $N0$ ，但是众所周知， $cbh$ 是一个眼高手低的人，所以你能帮助他解决这个问题吗？

， ， 为欧拉函数

输入格式

第一行一个整数 $T$ ，表示数据组数。 接下来每行，输入两个整数 $n$ 。

输出格式

对于每组数据，输出一个整数 $l$ ， 若不存在解就输出 $N0$ 。

样例

1
5

2

数据规模与约定

对于 $100$% 的数据， $n \le 1 \times 10^{18}$ ， $p = 1 \times 10^{9} + 7$