Rikka with Proper Fractions

Rikka is a lovely girl. Although she was not good at math before, she has made great progress with the help of her boyfriend Yuta. And Rikka has been able to do math research by herself now.

Today, Rikka is reading some materials about rational number approximation. Rikka is interested in the algorithm continuous fractional expansion which can find a closest fraction $\frac{a}{b}$ to approximate a given number $x$ among all the fractions with the denominator less than $n$.

Rikka wants to estimate the difficulty of this problem. She picks up a fraction $\frac{a}{b}$ which is less than $x$ and picks up a fraction $\frac{c}{d}$ which is larger than $x$. And she wants to find the number of rational numbers in the interval $[\frac{a}{b},\frac{c}{d}]$ which can be represented by fraction numbers with the denominator less than $n$. Formally, given $\frac{a}{b},\frac{c}{d},n$, Rikka wants to find out the number of proper fractions $\frac{e}{f}(1 \leq e < f \leq n, \text{gcd}(e,f)=1)$ which satisfy $\frac{a}{b} \leq \frac{e}{f} \leq \frac{c}{d}$.

This task seems too hard for Rikka. So, could you please help her to find out the answer?

The first line contains a single integer $t(1 \leq t \leq 10^3)$, the number of the testcases.

For each testcase, the first line contains five numbers $n,a,b,c,d(0 < \frac{a}{b} < \frac{c}{d} < 1, 1 \leq a,b,c,d \leq 10^8)$.

The input guarantees that both $\frac{a}{b}$ and $\frac{c}{d}$ are proper fraction numbers, $1 \leq n \leq 10^{10}$ and there are at most $3$ testcases with $n > 10^6$.

For each testcase, output a single line with a single integer, the answer modulo $998244353$.

3
5 1 2 3 4
10 1 2 7 9 
1000000 2 13 10000 10001

4
10
620740490

寒武纪ACM金牌训练营-重现赛