给定一个包含 $n$ 个整数的排列 $p$，这些整数的范围是 $1$ 到 $n$。你想要从 $p$ 构建一个序列 $a$。为此，你需要执行 $n$ 次以下操作：

• 将 $p$ 中的最小元素追加到 $a$ 的末尾；
• 移除 $p$ 的一端（左端或右端）。

给定一个随机排列 $p$。你的任务是计算通过上述方式可以得到的不同序列 $a$ 的数量。由于这个数字可能非常大，请输出其对 $998\,244\,353$ 取模的结果。如果两个序列在某个位置上的值不同，则认为它们是不同的。

大小为 $n$ 的排列是指包含 $1$ 到 $n$ 这 $n$ 个不同整数的序列。

输入格式

第一行包含一个整数 $t$ ($1 \le t \le 2 \cdot 10^5$)，表示测试用例的数量。接下来是各测试用例。 每个测试用例的第一行包含一个整数 $n$，表示排列的大小 ($1 \le n \le 2 \cdot 10^5$)。下一行包含该排列本身：$n$ 个 $1$ 到 $n$ 之间的不同整数。该排列由伪随机数生成器生成。

所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

输出格式

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

样例

样例输入 1

4
5
4 3 5 1 2
5
5 3 1 2 4
2
2 1
3
1 3 2

样例输出 1

8
7
2
4