하노이 탑 재장전

하노이 탑은 막대 3개와 지름이 $1, 2, \ldots, n$인 원판 $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, \ldots, x\_n$ ($x\_i \in \{ 1, 2, 3 \}$)이 주어진다. $x\_i$는 $i$번째 원판이 놓인 막대 번호이다. 셋째 줄에는 같은 형식으로 최종 배치가 주어진다.

모든 테스트 케이스의 $n$을 합하면 $10^5$를 넘지 않는다.

각 테스트 케이스마다 첫 번째 배치에서 두 번째 배치로 가는 데 필요한 최소 이동 횟수를 $998\,244\,353$으로 나눈 나머지로 출력한다.

이 변형에서는 어떤 두 배치든 서로 도달할 수 있다.