汉诺塔是一个著名的数学谜题，由三根杆子和 $n$ 个直径分别为 $1, 2, \dots, n$ 的圆盘组成。三根杆子上的圆盘均按直径从下到上递减的顺序堆叠，使得最小的圆盘始终位于最上方。一次合法的移动是指将一根杆子最上方的圆盘移动到另一根杆子的最上方。该移动必须保持排序规则：不能将较大的圆盘放在较小的圆盘上。原版谜题的目标是将所有圆盘从一根杆子移动到另一根杆子。

在这个变种谜题中，你只能在相邻的杆子之间移动圆盘：你可以在杆子 1 和 2 之间，以及杆子 2 和 3 之间移动圆盘，但不能在杆子 1 和 3 之间直接移动。

合法移动与非法移动示例

给定该谜题的两种状态，求从第一种状态到达第二种状态所需的最少移动次数。由于该数字可能很大，请输出其对 $998\,244\,353$ 取模的结果。

输入格式

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$ ($1 \le t \le 10^3$)。接下来是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$，表示涉及的圆盘数量 ($1 \le n \le 10^5$)。

第二行包含 $n$ 个整数 $x_1, x_2, \dots, x_n$，描述谜题的初始状态，其中 $x_i$ 是第 $i$ 个圆盘所在的杆子编号 ($x_i \in \{1, 2, 3\}$)。

第三行以相同的格式描述最终状态。

保证所有测试用例的 $n$ 之和不超过 $10^5$。

输出格式

对于每个测试用例，输出从第一种状态到达第二种状态所需的最少移动次数，对 $998\,244\,353$ 取模。

可以证明，在这个变种谜题中，任意两种状态之间都是可达的。

样例

输入 1

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

输出 1

2
7
20
0