有两个排列 $P_1, P_2, \dots, P_n$ 和 $Q_1, Q_2, \dots, Q_n$ 以及一个序列 $R$。初始时，$R$ 为空。当 $P$ 和 $Q$ 中至少有一个非空时，你需要选择一个非空数组（$P$ 或 $Q$），弹出其最左侧的元素，并将其附加到 $R$ 的末尾。最终，你将得到一个长度为 $2n$ 的序列 $R$。

给定一个长度为 $2n$ 的序列 $S$，请计算将 $P$ 和 $Q$ 合并为 $R$ 使得 $R = S$ 的方案数。当且仅当在某一步中选择的元素来自不同的数组时，两种方案被视为不同。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 300$)，表示测试用例的数量。对于每个测试用例： 第一行包含一个整数 $n$ ($1 \le n \le 300\,000$)，表示每个排列的长度。 第二行包含 $n$ 个不同的整数 $P_1, P_2, \dots, P_n$ ($1 \le P_i \le n$)。 第三行包含 $n$ 个不同的整数 $Q_1, Q_2, \dots, Q_n$ ($1 \le Q_i \le n$)。 第四行包含 $2n$ 个整数 $S_1, S_2, \dots, S_{2n}$ ($1 \le S_i \le n$)。

保证所有 $n$ 的总和不超过 $2\,000\,000$。

输出格式

对于每个测试用例，输出一行包含一个整数，表示可能的方案数。注意答案可能非常大，请输出其对 $998\,244\,353$ 取模的结果。

样例

样例输入 1

2
3
1 2 3
1 2 3
1 2 1 3 2 3
2
1 2
1 2
1 2 2 1

样例输出 1

2
0