M. Crystal Castle
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

$$$tarjen$$$ is the guardian of the Crystal Castle. The castle's corridor is inlaid with a row of $$$n$$$ magic crystals, where the $$$i$$$-th crystal has color number $$$a_i$$$. Adjacent crystals of the same color resonate and form a color segment — a maximal run of consecutive identical colors. For example, the color sequence $$$[1, 1, 2, 2, 1]$$$ has $$$3$$$ color segments: $$$[1, 1]$$$, $$$[2, 2]$$$, and $$$[1]$$$.

Every day, travelers come and ask $$$q$$$ questions. Each question specifies an interval $$$[l, r]$$$: if we take out these crystals, randomly shuffle them (choosing uniformly at random among all permutations with repetition), what is the expected number of color segments?

Output the answer modulo $$$998244353$$$. That is, if the answer is an irreducible fraction $$$\frac{p}{q}$$$, output $$$p \cdot q^{-1} \bmod 998244353$$$. It can be shown that $$$q^{-1} \bmod 998244353$$$ always exists under the constraints of this problem.

Input

The first line contains an integer $$$T$$$ ($$$1 \le T \le 100\,000$$$) — the number of test cases.

For each test case:

The first line contains two integers $$$n, q$$$ ($$$1 \le n, q \le 100\,000$$$) — the number of crystals and the number of queries.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$) — the color of each crystal.

The next $$$q$$$ lines each contain two integers $$$l, r$$$ ($$$1 \le l \le r \le n$$$) — the endpoints of the query interval.

The sum of $$$n$$$ over all test cases does not exceed $$$100\,000$$$, and the sum of $$$q$$$ does not exceed $$$100\,000$$$.

Output

For each query, output a single integer — the expected number of color segments modulo $$$998244353$$$.

Examples
Input
1
4 2
1 1 2 2
1 2
1 4
Output
1
3
Input
1
10 5
3 5 3 3 6 4 8 2 3 5
6 9
1 8
8 10
4 9
7 7
Output
4
748683272
3
665496241
1
Note

For the first sample:

The first query: the crystal colors taken out are $$$[1, 1]$$$. There is only one permutation, and the number of color segments is $$$1$$$.

The second query: the crystal colors taken out are $$$[1, 1, 2, 2]$$$. The $$$6$$$ permutations have color segment counts $$$2, 4, 3, 3, 4, 2$$$, and the expected value is $$$\frac{18}{6} = 3$$$.