Problem Background

Hakutaku K慧音 is giving lessons to the fairies at the Fog Lake.

One day, while teaching a math class, K慧音 introduced a very interesting notation: Knuth's Up-Arrow Notation. It can be used to describe extremely large numbers. Like Murasaki's age.

For non-negative integers \(a\), \(b\), and positive integer \(n\), the definition of Knuth's Up-Arrow Notation is:

\[a \uparrow^n b = \begin{cases} 1 & (b = 0) \\ a^b & (n = 1 \text{ and } b > 0) \\ a \uparrow^{n - 1} (a \uparrow^n (b - 1)) & (n > 1 \text{ and } b > 0) \end{cases}\]

Some simple examples:

• \(2 \uparrow 31 = 2^{31} = 2147483648\)
• \(2 \uparrow \uparrow 4 = 2^{2^{2^2}} = 2^{2^4} = 2^{16} = 65536\)

Notes:
1. \(a \uparrow b\) is the same as \(a \uparrow^1 b\);
2. \(a \uparrow \uparrow b\) is the same as \(a \uparrow^2 b\);
3. Please pay attention to the order of exponentiation.

Problem Description

K慧音 wants Kirino to solve the following equation about \(x\):

\[a \uparrow^n x \equiv b \pmod{p}\]

where \(a\), \(n\), \(b\), \(p\) are known constants, and \(x\) is the unknown.

Kirino is confused by Knuth's Up-Arrow Notation, but she doesn't want to be headbutted. Can you help her?

Input Format

This problem contains multiple test cases.

The first line contains an integer \(T\), the number of test cases.

For each test case:

One line containing four integers \(a\), \(n\), \(b\), \(p\).

Output Format

For each test case, output one line containing an integer. If the original equation has a solution, output the smallest non-negative integer solution; otherwise, output \(-1\).

Sample Input and Output

Sample Input #1

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

Sample Output #1

0
2
-1

Sample Input #2

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

Sample Output #2

2
-1
0

Sample Input #3

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

Sample Output #3

-1
3
0

Notes

This problem is bundled with subtasks.

For 100% of the data, \(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\).

见题面 Input 部分

见题面 Output 部分