Description

足球场上有 $n$ 名球员在传球。

最初，球在 $1$ 号球员脚下。之后每一秒，持球的球员必须把球传给其他任意一名球员。

Alice 想知道：有多少种传球方式，能够使得 $t$ 秒之后球重新回到 $1$ 号球员脚下。于是她向 Bob 求助。

现在，Bob 已经解决了这个问题，并算出了答案对 $998244353$ 取模的结果为 $x$。但是他忘了 $t$ 的具体数值。于是他向你求助：请找出最小的非负整数 $t$，使得 Alice 问题的答案对 $998244353$ 取模后等于 $x$。

Format

Input

第一行包含一个整数 $T$（$1 \leq T \leq 100$），表示测试数据的组数。

对于每组测试数据，一行包含两个整数 $n, x$（$2 \leq n \leq 10^6$，$0 \leq x < 998244353$）。

Output

对于每组测试数据，输出一行一个整数，表示最小的 $t$。如果这样的 $t$ 不存在，则输出 $-1$。

5
11 1
11 0
11 10
11 76805204
11 2

0
1
2
233333
-1

Source

2021“MINIEYE杯”中国大学生算法设计超级联赛（1）