410451: GYM104022 I The Answer!

Memory Limit:512 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

I. The Answer!time limit per test1 secondmemory limit per test512 megabytesinputstandard inputoutputstandard 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$$$.

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

加入题单

上一题 下一题 算法标签: