I. The Answer!
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

Millions of years ago, a very smart hyperspace race built a supercomputer, DeepThought. They gave DeepThought two positive integers $$$x$$$ and $$$y$$$, and let her calculate The Answer to Life, the Universe and Everything.

DeepThought didn't know how to calculate The Answer and she was in a hurry to watch TV, so she made a big integer using very complicated steps and no one would know how she got the result:

  • Firstly, DeepThought chose an integer $$$a$$$ greater than $$$1$$$.
  • Secondly, she calculated $$$\left(a^{F_x} - 1\right)$$$ and $$$\left(a^{F_y} - 1\right)$$$, denoted by $$$u$$$ and $$$v$$$ respectively, where $$$F_n$$$ is the $$$n$$$-th term of the Fibonacci sequence, given by the recursion: $$$F_1 = 1$$$, $$$F_2 = 1$$$ and $$$F_n = F_{n - 1} + F_{n - 2}$$$ for integer $$$n \ge 3$$$.
  • Lastly, she computed the ratio of these two numbers' least common multiple $$$\mathrm{lcm}(u, v)$$$ to their greatest common divisor $$$\mathrm{gcd}(u, v)$$$ as The Answer, which is obviously an integer.

Since she has gone for leisure activities, the task to calculate The Answer is left to you. For the secrecy of The Answer, you are only asked to report The Answer modulo $$$m$$$.

Input

The first line contains an integer $$$T$$$ $$$(1 \leq T \leq 10^4)$$$, indicating the number of test cases.

Then follow $$$T$$$ test cases. For each test case:

The only line contains four integers $$$x$$$, $$$y$$$, $$$a$$$ and $$$m$$$ $$$(1 \leq x, y \leq 10^9, 2 \leq a, m \leq 10^9)$$$.

Output

For each test case, output an integer in one line, representing The Answer modulo $$$m$$$.

Example
Input
3
3 3 3 97
7 3 2 1901
6 12 3 100
Output
1
1761
98
Note

For the first example case, $$$F_x = F_y = 2$$$, $$$u = v = a^2 - 1 = 8$$$, $$$\mathrm{lcm}(u, v) = \mathrm{gcd}(u, v) = 8$$$, so The Answer is $$$8 / 8 = 1$$$, and you need to report $$$1 \bmod 97 = 1$$$.

For the second example case, $$$F_x = 13$$$, $$$F_y = 2$$$, $$$u = a^{13} - 1 = 8191$$$, $$$v = a^2 - 1 = 3$$$, $$$\mathrm{lcm}(u, v) = 24573$$$, $$$\mathrm{gcd}(u, v) = 1$$$, so The Answer is $$$24573 / 1 = 24573$$$, and you need to report $$$24573 \bmod 1901 = 1761$$$.