题目描述

小Y想要成为天才数学少女。

一天她看到了这样一道题“给定$a$,$m$，求出$k$满足 $a^k \equiv k \pmod m$，或指出办不到”，却毫无头绪，成为了天才自闭少女。

你能帮助可怜的小Y解决这个问题吗？

输入格式

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

接下来$Q$行，每行两个整数$A_i, M_i$。

输出格式

$Q$行，每行一个不超过$2*10^{18}$的正整数表示答案，特别地，无解时输出$-1$。

样例

input

3
233 2333
2333 23333
100000 66666

output

1697
34150
33334

限制与约定

$Q \leq 100, 1 \leq A_i,M_i \leq 10^9$。

对于前$10\%$的数据，满足$M_i \leq 1000$。

对于前$20\%$的数据，满足$M_i \leq 100000$。

对于另外$40\%$的数据，满足$M_i$是质数。