题目描述

给定两个长度为 $n$ 的整数数组 $a$ 和 $b$。

你可以任选一组下标的子集，并对该子集中的每个下标 $i$ 同时交换 $a_i$ 与 $b_i$（也就是说，对于选中的每个 $i$ 执行一次交换 $(a_i,b_i)$ ）。如果在进行这些位置上的交换后，数组 $a$ 与数组 $b$ 都 非降序（即从左到右不减少），则该下标子集被称为 好子集。

你的任务是计算好子集的个数。由于结果可能很大，请对 $998244353$ 取模输出答案。

输入格式

第一行包含一个整数 $t$（$1\le t\le 500$）——测试用例数。

每个测试用例包含三行：

• 第一行包含一个整数 $n$（$1\le n\le 100$）。
• 第二行包含 $n$ 个整数 $a_1,a_2,\dots,a_n$（$1\le a_i\le 1000$）。
• 第三行包含 $n$ 个整数 $b_1,b_2,\dots,b_n$（$1\le b_i\le 1000$）。

额外保证：对于每个测试用例，至少存在一个好子集。

输出格式

对于每个测试用例，输出一行，包含一个整数 —— 好子集的个数，对 $998244353$ 取模。

样例输入

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

样例输出

2
2
8

说明

样例解释

• 第一个测试用例中，两个好子集为 $\{1,3\}$ 与 $\{2\}$。
• 第二个测试用例中，两个好子集为 $\{1\}$ 与 $\varnothing$（空集）。
• 第三个测试用例中的八个好子集列举见样例：$\{1,2,3,4,5\},\{1,2,3\},\{1,2,4,5\},\{1,2\},\{3,4,5\},\{3\},\{4,5\},\varnothing$。

数据范围

• $1\le t\le 500$
• $1\le n\le 100$
• $1\le a_i,b_i\le 1000$
• 对每个测试用例至少存在一个好子集。