Description

汉诺塔 是一个著名的数学谜题，由三根柱子和 $n$ 个直径分别为 $1, 2, \ldots, n$ 的圆盘组成。每根柱子上都叠放着若干圆盘，从上到下直径依次递减，因此最小的圆盘总是在顶部。一个合法的移动操作是将某根柱子上最小的圆盘移动到另一根柱子的顶部。这个移动必须保持有序性：不能将较大的圆盘放在较小的圆盘上。原版谜题的目标是将所有圆盘从一根柱子移动到另一根柱子。

在这个变体版本中，你只能 在相邻柱子之间 移动圆盘：可以在柱子 $1$ 和 $2$ 之间移动，也可以在柱子 $2$ 和 $3$ 之间移动，但不能直接在柱子 $1$ 和 $3$ 之间移动。

给定汉诺塔的两个状态，求从初始状态到达目标状态所需的最少移动次数。由于这个数字可能很大，请输出其对 $998\,244\,353$ 取模的结果。

Input Format

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

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

第二行包含 $n$ 个整数 $x_1, x_2, \ldots, x_n$，描述初始状态，其中 $x_i$ 表示第 $i$ 个圆盘所在的柱子（$x_i \in \{ 1, 2, 3 \}$）。

第三行以相同格式描述目标状态。

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

Output Format

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

可以证明，在这个变体版本中，任何两个状态之间都是可以相互转换的。

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

2
7
20
0