题目描述

汉诺塔是一道经典数学谜题，由三根柱子和 $n$ 个直径分别为 $1,2,\ldots,n$ 的圆盘组成。

每根柱子上的圆盘都按直径从下到上严格递减，因此最小的圆盘总在最上方。一次合法操作是：取下某根柱子最上方的圆盘，将其放到另一根柱子的顶部，并且操作后仍必须满足不能把大圆盘放在小圆盘上。

在本题的变体中，只允许在相邻柱子之间移动圆盘：

• 可以在柱子 $1$ 和柱子 $2$ 之间移动；
• 可以在柱子 $2$ 和柱子 $3$ 之间移动；
• 不允许直接在柱子 $1$ 和柱子 $3$ 之间移动。

给定该谜题的两个合法状态，请求出从第一个状态变为第二个状态所需的最少操作次数。答案可能很大，请对 $998\,244\,353$ 取模。

输入格式

每个输入包含多组测试数据。

第一行包含一个整数 $t$，表示测试数据组数。

对于每组测试数据：

• 第一行包含一个整数 $n$，表示圆盘数量；
• 第二行包含 $n$ 个整数 $x_1,x_2,\ldots,x_n$，描述初始状态，其中 $x_i$ 表示直径为 $i$ 的圆盘位于哪一根柱子上；
• 第三行以相同格式描述目标状态。

数据范围

所有测试数据的 $n$ 之和不超过 $10^5$。

输出格式

对于每组测试数据，输出从初始状态到目标状态所需的最少操作次数对 $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