Define $F(x, a, b) = \gcd(x^a - 1, x^b - 1) + 1$, where $x > 0$. Specifically, if $a = 0$ or $b = 0$, $F(x, a, b) = 0$.
Given five non-negative integers $m, a, b, c, d$. Let $L = F(m, a, b) + 1$ and $R = F(m, c, d)$. Determine how many subsets of the set $\{L, L + 1, L + 2, \dots, R - 2, R - 1, R\}$ have a sum that is a multiple of $m$. Since the answer may be very large, output the result modulo $998244353$.
Input
The first line contains an integer $T$, representing the number of test cases. The next $T$ lines each contain five non-negative integers $m, a, b, c, d$.
Output
For each test case, output the answer.
Examples
Input 1
3 5 0 0 2 1 4 1 2 2 4 8 3 2 4 6
Output 1
8 1024 527847872
Note
After calculation, $L=1, R=5$. The set is $\{1, 2, 3, 4, 5\}$. The subsets whose sum is a multiple of $5$ are the following $8$: $\{\}, \{5\}, \{2, 3\}, \{1, 4\}, \{1, 2, 3, 4\}, \{2, 3, 5\}, \{1, 4, 5\}, \{1, 2, 3, 4, 5\}$
Constraints
| Data Point ID | $m$ | $L$ | $R$ | $a$ | $b$ | $c$ | $d$ | $T$ | Special Property |
|---|---|---|---|---|---|---|---|---|---|
| 1 | $m=2$ | $L=1$ | $R=2$ | $a=0$ | $b=0$ | $c \le 10$ | $d \le 10$ | $T \le 5$ | None |
| 2 | $m \le 10$ | $L=1$ | $R=m$ | $a=0$ | $b=0$ | $c \le 10$ | $d \le 10$ | $T \le 5$ | None |
| 3 | $m \le 5$ | $L \le 10^3$ | $R \le 10^3$ | $a \le 10$ | $b \le 10$ | $c \le 10$ | $d \le 10$ | $T \le 5$ | 1 |
| 4-6 | $m \le 20$ | $L \le 2 \times 10^3$ | $R \le 2 \times 10^3$ | $a \le 10$ | $b \le 10$ | $c \le 10$ | $d \le 10$ | $T \le 5$ | None |
| 7 | $m \le 20$ | $L \le 10^5$ | $R \le 10^5$ | $a \le 10^2$ | $b \le 10^2$ | $c \le 10^2$ | $d \le 10^2$ | $T \le 5$ | 2 |
| 8,9 | $m \le 80$ | $L \le 10^9$ | $R \le 10^9$ | $a \le 10^2$ | $b \le 10^2$ | $c \le 10^2$ | $d \le 10^2$ | $T \le 5$ | None |
| 10-13 | $m \le 2 \times 10^3$ | $L \le 10^{18}$ | $R \le 10^{18}$ | $a \le 10^3$ | $b \le 10^3$ | $c \le 10^3$ | $d \le 10^3$ | $T \le 5$ | None |
| 14-17 | $m \le 10^5$ | $L \le 10^{18}$ | $R \le 10^{18}$ | $a \le 10^3$ | $b \le 10^3$ | $c \le 10^3$ | $d \le 10^3$ | $T \le 5$ | None |
| 18-20 | $m \le 10^7$ | $L \le 10^{18}$ | $R \le 10^{18}$ | $a \le 10^3$ | $b \le 10^3$ | $c \le 10^3$ | $d \le 10^3$ | $T \le 10^4$ | None |
Special Property 1: $R - L + 1 \le 20$; Special Property 2: $R - L + 1 \le 2000$ For all data, it is guaranteed that $L < R$ and $m > 0$.