AT_arc221_a.Two Arithmetic Progressions

You are given positive integers $N,A,B,C,D$.

Find $\displaystyle \sum_{i=1}^N \gcd (Ai+B,Ci+D)$, modulo $998244353$. Here, $\gcd(x,y)$ denotes the greatest common divisor of $x$ and $y$.

You are given $T$ test cases; solve each of them.

给定正整数 $N,A,B,C,D$。

求 $\displaystyle \sum_{i=1}^N \gcd (Ai+B,Ci+D)$ 对 $998244353$ 取模的值。其中，$\gcd(x,y)$ 表示 $x$ 与 $y$ 的最大公约数。

你将得到 $T$ 组测试用例；请分别求解每一组。

The input is given from Standard Input in the following format:

$T$
$\text{case}_1$
$\text{case}_2$
$\vdots$
$\text{case}_T$

Each test case is given in the following format:

$N$ $A$ $B$ $C$ $D$

输入从标准输入中按以下格式给出：

$T$
$\text{case}_1$
$\text{case}_2$
$\vdots$
$\text{case}_T$

每个测试用例按以下格式给出：

$N$ $A$ $B$ $C$ $D$

Output the answers for the test cases in order, separated by newlines.

按顺序输出测试用例的答案，答案之间用换行符分隔。

Sample 1 Explanation:
For the first test case, the answer is $\gcd(4,6)+\gcd(5,10)+\gcd(6,14)+\gcd(7,18)=2+5+2+1=10$.

Constraints

• $1\leq T\leq 200$
• $1\leq N\leq 10^9$
• $1\leq A,B,C,D\leq 10^4$
• All input values are integers.

样例 1 解释：
对于第一个测试用例，答案为 $\gcd(4,6)+\gcd(5,10)+\gcd(6,14)+\gcd(7,18)=2+5+2+1=10$。

约束条件

• $1\leq T\leq 200$
• $1\leq N\leq 10^9$
• $1\leq A,B,C,D\leq 10^4$
• 所有输入值均为整数。