题目背景

上白泽慧音在给雾之湖的妖精们讲课。

某天，慧音在上数学课时，提到了一种非常有趣的记号：高德纳箭号表示法。它可以用来描述非常巨大的数字。比如紫的年龄。

对于非负整数 $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$。

3
2 1 1 3
3 1 2 7
7 1 2 4

0
2
-1

3
2 2 4 7
3 2 4 6
5 2 1 3

2
-1
0

3
4 3 5 8
2 3 9 11
6 3 1 5

-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$。