数百万年前，一个非常聪明的超空间种族建造了一台超级计算机 DeepThought。他们给了 DeepThought 两个正整数 $x$ 和 $y$，并让她计算“生命、宇宙以及一切的答案”（The Answer）。

DeepThought 不知道如何计算这个答案，而且她急着去看电视，于是她通过非常复杂的步骤制造了一个大整数，没人知道她是如何得到这个结果的：

• 首先，DeepThought 选择了一个大于 1 的整数 $a$。
• 其次，她计算了 $a^{F_x} - 1$ 和 $a^{F_y} - 1$，分别记为 $u$ 和 $v$，其中 $F_n$ 是斐波那契数列的第 $n$ 项，由递归式给出：$F_1 = 1, F_2 = 1$ 且对于整数 $n \ge 3$ 有 $F_n = F_{n-1} + F_{n-2}$。
• 最后，她计算了这两个数的最小公倍数 $\text{lcm}(u, v)$ 与它们的最大公约数 $\text{gcd}(u, v)$ 的比值作为“答案”，这显然是一个整数。

由于她已经去进行休闲活动了，计算“答案”的任务就交给你了。为了保密起见，你只需要报告“答案”对 $m$ 取模的结果。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 10^4$)，表示测试用例的数量。 接下来是 $T$ 个测试用例。每个测试用例： 唯一的一行包含四个整数 $x, y, a$ 和 $m$ ($1 \le x, y \le 10^9, 2 \le a, m \le 10^9$)。

输出格式

对于每个测试用例，输出一行一个整数，表示“答案”对 $m$ 取模的结果。

样例

输入 1

3
3 3 3 97
7 3 2 1901
6 12 3 100

输出 1

1
1761
98

说明

对于第一个样例，有 $F_x = F_y = 2$，$u = v = a^2 - 1 = 8$，$\text{lcm}(u, v) = \text{gcd}(u, v) = 8$，因此“答案”为 $8/8 = 1$，你需要报告 $1 \pmod{97} = 1$。

对于第二个样例，有 $F_x = 13, F_y = 2$，$u = a^{13} - 1 = 8191, v = a^2 - 1 = 3$，$\text{lcm}(u, v) = 24573$，$\text{gcd}(u, v) = 1$，因此“答案”为 $24573/1 = 24573$，你需要报告 $24573 \pmod{1901} = 1761$。