P5702 Harmonic Series Summation

Given $n, p$, find the value of: $$\sum_{i=1}^n \frac 1i $$ modulo $p$. If you do not know how to take a fraction modulo a number, you can refer to [this problem](https://www.luogu.com.cn/problem/P2613). It is guaranteed that the answer exists modulo $p$. To make your computation easier, the smallest primitive root $g$ of $p$ will be provided.

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 $T$ lines. Each line contains one integer, the answer.

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