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