Koxia 和 Mahiru 正在玩一个游戏,其中包含三个长度为 $$$n$$$ 的数组 $$$a$$$、$$$b$$$ 和 $$$c$$$。 $$$a$$$、$$$b$$$ 和 $$$c$$$ 的每个元素都是 $$$1$$$ 和 $$$n$$$ 之间的整数(包括 $$$1$$$ 和 $$$n$$$)。
游戏由 $$$n$$$ 轮组成。在第 $$$i$$$ 轮中,他们执行以下动作:
- 令 $$$S$$$ 为多重集 $$$\{a_i, b_i, c_i\}$$$。
- Koxia 根据她的选择从多重集中 $$$S$$$ 中删除了一个元素。
- Mahiru 从多重集合 $$$S$$$ 中剩余的两个整数中选择一个整数。
令 $$$d_i$$$ 为 Mahiru 在第 $$$i$$$ 轮中选择的整数。如果 $$$d$$$ 是排列$$$^\dagger$$$,则 Koxia 获胜。否则,真昼就赢了。
目前,仅选择了数组 $$$a$$$ 和 $$$b$$$。作为 Koxia 的狂热支持者,您希望选择一个数组 $$$c$$$ 以便 Koxia 获胜。计算这样的 $$$c$$$ 的数量,以 $$$998\,244\,353$$$ 为模。
请注意,Koxia 和 Mahiru 都发挥最佳状态。
$$$^\dagger$$$ 长度 $$$n$$$ 的排列是一个数组,由从 $$$1$$$ 到 $$$n$$$ 的 $$$n$$$ 不同整数组成,且顺序任意。例如,$$$[2,3,1,5,4]$$$是一个排列,但$$$[1,2,2]$$$不是排列($$$2$$$在数组中出现两次),$$$[1,3,4]$$$也不是排列($$$n=3$$$但数组中有$$$4$$$)。
输入
每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 2 \cdot 10^4$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq {10}^5$$$) — 数组的大小。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \leq a_i \leq n$$$)。
每个测试用例的第三行包含 $$$n$$$ 整数 $$$b_1, b_2, \dots, b_n$$$ ($$$1 \leq b_i \leq n$$$)。
保证所有测试用例的$$$n$$$总和不超过$$${10}^5$$$。
输出
输出一个整数 - $$$c$$$ 的数量使 Koxia 获胜,模 $$$998\,244\,353$$$。
示例
输入 #1
2 3 1 2 2 1 3 3 5 3 3 1 3 4 4 5 2 5 5
输出 #1
6 0
注意
在第一个测试用例中,有 $$$6$$$ 可能的数组 $$$c$$$ 使 Koxia 获胜 — $$$[1, 2, 3]$$$, $$$[1, 3, 2]$$$, $$$[2, 2, 3]$$$, $$$[2, 3, 2]$$$, $$$[3, 2, 3]$$$,$$$[3,3,2]$$$。
在第二个测试用例中,可以证明没有数组 $$$c$$$ 能让 Koxia 获胜。