「Wdsr-2」白泽教育
题目背景
上白泽慧音在给雾之湖的妖精们讲课。
某天，慧音在上数学课时，提到了一种非常有趣的记号：**高德纳箭号表示法**。它可以用来描述非常巨大的数字。~~比如紫的年龄。~~
对于非负整数 $a, b$ 和正整数 $n$，高德纳箭号表示法的定义为：
$$a \uparrow^n b = \begin{cases}
1\ (b = 0) \\
a^b\ (n = 1\ \operatorname{and}\ b > 0) \\
a \uparrow^{n - 1} (a \uparrow^n (b - 1))\ (n > 1\ \operatorname{and}\ b > 0)
\end{cases}$$
一些简单的例子：
- $2 \uparrow 31 = 2^{31} = 2147483648$
- $2 \uparrow \uparrow 4 = 2^{2^{2^2}} = 2^{2^4} = 2^{16} = 65536$
注：
1. $a \uparrow b$ 与 $a \uparrow^1 b$ 相同；
2. $a \uparrow \uparrow b$ 与 $a \uparrow^2 b$ 相同；
3. 请注意幂运算的顺序。
题目描述
慧音希望琪露诺解决以下关于 $x$ 的方程：
$$a \uparrow^n x \equiv b \pmod p$$
其中，$a, n, b, p$ 为已知的常数，$x$ 为未知数。
琪露诺被高德纳箭号表示法搞得云里雾里的，但是她不想被头槌。你能帮帮她吗？
输入输出格式
输入格式
**本题有多组测试数据。**
第一行，一个整数 $T$，表示数据组数。
对于每组数据：
一行，四个整数 $a, n, b, p$。
输出格式
对于每组数据，输出一行，一个整数，如果原方程有解，输出该方程的最小非负整数解；否则，输出 $-1$。
输入输出样例
输入样例 #1
3
2 1 1 3
3 1 2 7
7 1 2 4输出样例 #1
0
2
-1输入样例 #2
3
2 2 4 7
3 2 4 6
5 2 1 3输出样例 #2
2
-1
0输入样例 #3
3
4 3 5 8
2 3 9 11
6 3 1 5输出样例 #3
-1
3
0说明
**本题开启捆绑测试。**
| Subtask | $n$ | $p$ | $T$ | 分值 | 时限 |
| :------: | :------: | :------: | :------: | :------: | :------: |
| $1$ | $n = 1$ | $2 \leq p \leq 10^9$ 且 $p$ 为质数 | $1 \leq T \leq 100$ | $15 \operatorname{pts}$ | $2.00 \operatorname{s}$ |
| $2$ | $n = 2$ | 无特殊限制 | $1 \leq T \leq 5 \times 10^3$ | $25 \operatorname{pts}$ | $1.00 \operatorname{s}$ |
| $3$ | $n = 3$ | 无特殊限制 | 无特殊限制 | $60 \operatorname{pts}$ | $2.00 \operatorname{s}$ |
对于 $100\%$ 的数据，$1 \leq a \leq 10^9$，$1 \leq n \leq 3$，$0 \leq b < p \leq 10^9$，$1 \leq T \leq 2 \times 10^4$。