Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Bakana

Limits: 1s, 1.0 GB

Given four positive integers $N, a, b, M$, find the value of $GCD(N^a-1, N^b-1)$ modulo $M$.

Here, $GCD(x,y)$ is a function that returns the greatest common divisor of $x$ and $y$. In mathematics, the greatest common divisor of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers. For example, $GCD(8,12) = 4$.

Input

The first line of the input contains an integer $T$ denoting the number of test cases. $T$ lines follow. Each of these lines contains four integers $N, a, b, M$.

Constraints:

$1\leq T\leq 10^5$
$2\leq N\leq 10^9$
$1\leq a\leq 10^9$
$1\leq b\leq 10^9$
$1\leq M\leq 10^9$

Output

For each test case, print the value of $GCD(N^a-1, N^b-1)$ modulo $M$ on a separate line.
Please check the sample IO for the correct format.

Samples

InputOutput
2
2 1 2 10
3 6 9 10
1
6

In Case #01, we have to find
$GCD(2^1-1,2^2-1) = GCD(1,3) = 1$
Since the result is less than $10$, we do not need any modulo operation.

In Case #02, we have to find
$GCD(3^6-1,3^9-1) = GCD(728,19682) = 26$
Here, we can apply the modulo operation to get the result: $(26\mod 10) = 6$.

Discussion
Submit

Login to submit

Editorial

Login to unlock editorial