P6736 "Wdsr-2" Baize Education

上白泽慧音在给雾之湖的妖精们讲课。 某天，慧音在上数学课时，提到了一种非常有趣的记号：**高德纳箭号表示法**。它可以用来描述非常巨大的数字。~~比如紫的年龄。~~ 对于非负整数 $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$ 为未知数。 琪露诺被高德纳箭号表示法搞得云里雾里的，但是她不想被头槌。你能帮帮她吗？

**This problem contains multiple test cases.** The first line contains an integer $T$, the number of test cases. For each test case: One line contains four integers $a, n, b, p$.

For each test case, output one line with one integer. If the original equation has a solution, output the smallest non-negative integer solution; otherwise, output $-1$.

**This problem uses bundled evaluation.** | Subtask | $n$ | $p$ | $T$ | Score | Time Limit | | :------: | :------: | :------: | :------: | :------: | :------: | | $1$ | $n = 1$ | $2 \leq p \leq 10^9$ and $p$ is prime | $1 \leq T \leq 100$ | $15 \operatorname{pts}$ | $2.00 \operatorname{s}$ | | $2$ | $n = 2$ | No special constraints | $1 \leq T \leq 5 \times 10^3$ | $25 \operatorname{pts}$ | $1.00 \operatorname{s}$ | | $3$ | $n = 3$ | No special constraints | No special constraints | $60 \operatorname{pts}$ | $2.00 \operatorname{s}$ | For $100\%$ of the testdata, $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$. Translated by ChatGPT 5