# Practice on Toph

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

## Bakana

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

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

.

Login to submit

Login to unlock editorial