Hanoi Towers Reloaded

The Towers of Hanoi is a famous mathematical puzzle with three rods and $n$ disks of diameters $1, 2, \ldots, n$. Each rod holds some disks stacked in decreasing order of diameter from bottom to top, so the smallest disk is always on top. A valid move takes the smallest disk from a rod and places it on top of another rod. The order must stay sorted, so you cannot put a larger disk onto a smaller one. The original goal is to move all disks from one rod to another.

In this variation, you can only move disks between adjacent rods. You can move a disk between rods $1$ and $2$, and between rods $2$ and $3$, but not between rods $1$ and $3$.

Valid move	Invalid move: non-adjacent rods	Invalid move: moving a larger disk onto a smaller one

Given two configurations of this puzzle, find the minimum number of moves needed to go from the first configuration to the second. The answer can be large, so print it modulo $998\,244\,353$.

The first line contains the number of test cases $t$ ($1 \le t \le 10^3$). Each test case follows.

The first line of each test case contains an integer $n$ ($1 \le n \le 10^5$), the number of disks.

The second line contains $n$ integers $x\_1, x\_2, \ldots, x\_n$ ($x\_i \in \{ 1, 2, 3 \}$), where $x\_i$ is the rod holding the $i$-th disk. The third line describes the final configuration in the same format.

The sum of $n$ over all test cases does not exceed $10^5$.

For each test case, print the minimum number of moves needed to go from the first configuration to the second, modulo $998\,244\,353$.

Any two configurations can reach each other in this variation.