——前路漫漫，向下延伸 ——一场宏大而神奇的嘉年华！ ——无视那黑暗而阴森的森林 ——无视那闪烁而凝视的眼睛 ——充满乐趣与奇观！ ——音乐与烟火点亮黑夜！ ——别停下！你快到了！ ——看吧，我的朋友：暗月马戏团！

有一天，你和朋友们去了暗月马戏团。 你们开始玩一个叫“寻找荒谬划分”的游戏！ 如果一个数组的最大值位于奇数下标，且最小值位于偶数下标，则称该数组是“荒谬的”。 给定一个长度为 $n$ 的序列 $a$。保证所有 $a_i$ 两两不同。 你可以将该序列划分为若干个（可能为一个）连续区间，使得这些区间互不相交，且每个位置恰好属于一个区间。对于每个区间，我们可以将其视为一个从 1 开始下标的数组。如果划分后的每个区间对应的数组都是“荒谬的”，则称该划分是“荒谬的”。 请计算给定序列的“荒谬划分”的数量。 由于答案可能非常大，你只需要输出答案对 998244353 取模的结果。

输入格式

输入包含多个测试用例。 第一行包含一个整数 $T$ ($1 \le T \le 5$)，表示测试用例的数量。 对于每个测试用例，第一行包含一个整数 $n$ ($1 \le n \le 3 \times 10^5$)。 第二行包含 $n$ 个整数 $a_i$ ($1 \le a_i \le 10^9$)，保证对于所有 $i \neq j$，$a_i \neq a_j$。 所有测试用例的 $n$ 之和不超过 $10^6$。

输出格式

对于每个测试用例，输出一行，包含答案对 998244353 取模的结果。

样例

样例输入 1

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

样例输出 1

2
5