Rikka 是一个可爱的女孩。虽然她以前数学不好，但在男朋友 Yuta 的帮助下，她取得了很大的进步，现在已经能够独立进行数学研究了。

今天，Rikka 正在阅读一些关于有理数逼近的资料。她对连分数展开算法很感兴趣，该算法可以在所有分母小于 $n$ 的分数中找到最接近给定数 $x$ 的分数 $\frac{a}{b}$。

Rikka 想要评估这个问题的难度。她选取了一个小于 $x$ 的分数 $\frac{a}{b}$ 和一个大于 $x$ 的分数 $\frac{c}{d}$。她想找出区间 $[\frac{a}{b}, \frac{c}{d}]$ 中分母小于或等于 $n$ 的有理数的个数。形式化地说，给定 $\frac{a}{b}$、$\frac{c}{d}$ 和 $n$，Rikka 想要找到满足 $\frac{a}{b} \le \frac{e}{f} \le \frac{c}{d}$ 的真分数 $\frac{e}{f}$ ($1 \le e < f \le n, \gcd(e, f) = 1$) 的个数。

这个任务对 Rikka 来说似乎太难了。请帮她找到答案。

输入格式

第一行包含一个整数 $t$ ($1 \le t \le 10^3$)，表示测试用例的数量。

每个测试用例占一行，包含五个整数 $n, a, b, c, d$ ($0 < \frac{a}{b} < \frac{c}{d} < 1, 1 \le a, b, c, d \le 10^8$)。

保证 $\frac{a}{b}$ 和 $\frac{c}{d}$ 均为真分数，$1 \le n \le 10^{10}$，且至多有 3 个测试用例满足 $n > 10^6$。

输出格式

对于每个测试用例，输出一行，包含一个整数：答案对 $998\,244\,353$ 取模的结果。

样例

输入 1

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

输出 1

4
10
620740490