Description

Given $n, p$, find the value of:

modulo $p$.

If you do not know how to take a fraction modulo a number, you can refer to this problem.
It is guaranteed that the answer exists modulo $p$.

To make your computation easier, the smallest primitive root $g$ of $p$ will be provided.

Input Format

The first line contains a positive integer $T$, the number of test cases.
The next $T$ lines each contain three positive integers $n, p, g$.

Output Format

Output $T$ lines. Each line contains one integer, the answer.

5
998007 998244353 3
19260817 998244353 3
274829164 998244353 3
792846153 998244353 3
1924762 899678209 7

429767635
632288905
445668022
128133635
3097708

Hint

Constraints
For $30\%$ of the testdata, $1\le n \le 10^6$.
For $100\%$ of the testdata, $1 \le n < p < 2^{30}$, $1\le T \le 20$.
It is guaranteed that $p$ is prime, and $p-1$ is divisible by $2^{19}$.

Note: The time limit is three times that of std. If you cannot pass, please check that your time complexity is correct and optimize the constant factors.

Translated by ChatGPT 5