在对合数 $M = \prod p_i^{t_i}$ 取模进行整数乘法时，我们可以通过对 $M$ 的每个互质分量 $p_i^{t_i}$ 分别进行计算，然后使用广东剩余定理（CRT）合并结果以获得最终答案，从而加速这一过程。

不幸的是，在代码运行时，其中一个互质分量的计算发生了错误。也就是说，对于某个 $i$，它在模 $p_i^{t_i}$ 意义下得到的结果是不正确的，因此合并后的答案也是错误的。

给定要相乘的两个数 $A, B$，以及错误答案 $C'$ 和模数 $M$，你需要找到程序出错的那个分量。

输入格式

第一行包含一个整数 $T \, (1 \le T \le 10^6)$，表示测试用例的数量。

接下来的 $T$ 行，每行包含 $4$ 个整数 $A, B, C', M \, (0 \le A, B, C' < M \le 10^{18})$，表示一次查询。

输出格式

输出 $T$ 行。每行包含一个整数 $p_i^{t_i}$，表示程序出错的那个分量。

样例

输入样例 1

1
2 3 1 10

输出样例 1

2

说明

$$M = 10 = 2^1 \times 5^1$$

$$(2 \times 3) \bmod 2^1 = 0 \neq 1$$

$$(2 \times 3) \bmod 5^1 = 1$$

因此，答案是 $2^1$。