F. Equations
time limit per test
2.5 с
memory limit per test
1024 МБ
input
standard input
output
standard output

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$$$.

Input

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

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

Example
Input
5
5 4 3
5 3 4
10 5 8
10 8 5
100 79 97
Output
2
3
15
10
2519