P5176 Greatest Common Divisor.

In the last five minutes before collecting the papers, pg found that there was still a major problem on the back side of the paper.

Compute [](https://www.luogu.org/paste/zltm8ddt) Since the answer may be too large, output the value of the answer modulo $10^9+7$.

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

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

For the first $10\%$ of the testdata, $T = 5$, and $40 \le n, m, p \le 100$. For another $20\%$ of the testdata, $T = 50$, and $100 \le n, m, p \le 5 \times 10^4$. For another $20\%$ of the testdata, $T = 20$, and $4 \times 10^6 \le n, m, p \le 5 \times 10^6$. For the remaining $50\%$ of the testdata, $T = 10^3$, and $10^7 \le n, m, p \le 2 \times 10^7$. Translated by ChatGPT 5