Description

慧音希望琪露诺解决以下关于 $x$ 的方程：

其中，$a, n, b, p$ 为已知的常数，$x$ 为未知数。

琪露诺被高德纳箭号表示法搞得云里雾里的，但是她不想被头槌。你能帮帮她吗？

Input Format

本题有多组测试数据。

第一行，一个整数 $T$，表示数据组数。

对于每组数据：

一行，四个整数 $a, n, b, p$。

Output Format

对于每组数据，输出一行，一个整数，如果原方程有解，输出该方程的最小非负整数解；否则，输出 $-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

本题开启捆绑测试。

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