题目描述

给定 $n,p$，求：

对 $p$ 取模的值。

如果你不知道怎么对分数取模，可以看这题。
保证答案在模 $p$ 意义下存在。

为了方便你的计算，这里将给出 $p$ 的最小原根 $g$。

输入格式

输入第一行一个正整数 $T$，表示数据组数。
接下来 $T$ 行，每行三个正整数 $n,p,g$。

输出格式

输出 $T$ 行，每行一个整数表示答案。

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

429767635
632288905
445668022
128133635
3097708

提示

【数据范围】
对于 $30\%$ 的数据，$1\le n \le 10^6$；
对于 $100\%$ 的数据，$1 \le n < p < 2^{30}$，$1\le T \le 20$。
保证 $p$ 为质数，且 $p-1$ 可以被 $2^{19}$ 整除。

注：时限为 std 的三倍，如果过不去请确认时间复杂度正确，并优化常数。