tarjen 是水晶城堡的守护者。城堡的走廊上镶嵌着一排 $n$ 个魔法水晶，其中第 $i$ 个水晶的颜色编号为 $a_i$。相邻的同色水晶会产生共鸣并形成一个颜色段（color segment）——即最长的连续相同颜色序列。例如，颜色序列 $[1, 1, 2, 2, 1]$ 有 $3$ 个颜色段：$[1, 1]$、$[2, 2]$ 和 $[1]$。

每天都有旅行者来提出 $q$ 个问题。每个问题指定一个区间 $[l, r]$：如果我们取出这些水晶，并将它们随机打乱（在所有含重复元素的全排列中等概率随机选择一个），那么颜色段数量的期望值是多少？

输出答案对 $998244353$ 取模的结果。也就是说，如果答案是一个最简分数 $\frac{p}{q}$，输出 $p \cdot q^{-1} \bmod 998244353$。可以证明，在本题的限制条件下，$q^{-1} \bmod 998244353$ 总是存在。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 100\,000$) — 测试用例的数量。

对于每个测试用例：

第一行包含两个整数 $n, q$ ($1 \le n, q \le 100\,000$) — 水晶的数量和询问的数量。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$) — 每个水晶的颜色。

接下来的 $q$ 行，每行包含两个整数 $l, r$ ($1 \le l \le r \le n$) — 询问区间的端点。

所有测试用例中 $n$ 的总和不超过 $100\,000$，且 $q$ 的总和不超过 $100\,000$。

输出格式

对于每个询问，输出一个整数 — 颜色段数量的期望值对 $998244353$ 取模的结果。

样例

输入样例 1

1
4 2
1 1 2 2
1 2
1 4

输出样例 1

1
3

输入样例 2

1
10 5
3 5 3 3 6 4 8 2 3 5
6 9
1 8
8 10
4 9
7 7

输出样例 2

4
748683272
3
665496241
1

说明

对于第一个样例：

第一个询问：取出的水晶颜色为 $[1, 1]$。只有一种排列，颜色段数量为 $1$。

第二个询问：取出的水晶颜色为 $[1, 1, 2, 2]$。这 $6$ 种排列的颜色段数量分别为 $2, 4, 3, 3, 4, 2$，期望值为 $\frac{18}{6} = 3$。