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 contains four integers $a, n, b, p$.

Output Format

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

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

Hint

This problem uses bundled evaluation.

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