410451: GYM104022 I The Answer!

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

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

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

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

1
1761
98

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