调和级数求和
题目描述
给定 $n,p$，求：
$$\sum_{i=1}^n \frac 1i $$
对 $p$ 取模的值。
如果你不知道怎么对分数取模，可以看[这题](https://www.luogu.com.cn/problem/P2613)。
保证答案在模 $p$ 意义下存在。
为了方便你的计算，这里将给出 $p$ 的最小原根 $g$。
输入输出格式
输入格式
输入第一行一个正整数 $T$，表示数据组数。
接下来 $T$ 行，每行三个正整数 $n,p,g$。
输出格式
输出 $T$ 行，每行一个整数表示答案。
输入输出样例
输入样例 #1
5
998007 998244353 3
19260817 998244353 3
274829164 998244353 3
792846153 998244353 3
1924762 899678209 7输出样例 #1
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 的三倍，如果过不去请确认时间复杂度正确，并优化常数。