410572: GYM104053 F Equations

Let $$$f(a,b,m)$$$ be the least non-negative solution of the congruence equation:

$$$$$$ ax\equiv b \pmod m $$$$$$

If there isn't a solution, then $$$f(a,b,m)=0$$$.

Given $$$n$$$, $$$a$$$, $$$b$$$, calculate $$$\displaystyle \sum_{i=1}^{n} f(a,b,i) \bmod 998244353$$$.

The first line contains an integer $$$T$$$ ($$$1\leq T\leq 5$$$) denoting the number of test cases.

Then $$$T$$$ lines follow, each containing three positive integers $$$n$$$, $$$a$$$, $$$b$$$ ($$$1\le n\leq 10^{18}$$$, $$$1\le a,b\leq 10^6$$$).

Output $$$T$$$ lines. The $$$i$$$-th line contains the answer of the $$$i$$$-th test case.

5
5 4 3
5 3 4
10 5 8
10 8 5
100 79 97

2
3
15
10
2519