問題文

ハノイの塔は、3 本の杭と、大きさが互いに異なる N 個の円盤からなるパズルです。 3 本の杭にはそれぞれ 1, 2, 3 の番号が付けられています。 また、N 個の円盤を、小さい方から順に円盤 1, 2, \dots, N と呼びます。

どの時点においても、すべての円盤はいずれかの杭に刺さっていなければならず、各杭においては下から上に向かって円盤が小さくなるように積まれている必要があります。 1 回の操作で、ある杭の一番上にある円盤を 1 つ選び、別の空の杭、もしくは移動する円盤よりも大きな円盤が一番上にある杭に移動させることができます。

ハノイの塔のとり得る状態の組 (X, Y) に対して、状態 X から状態 Y へ最小の操作回数で到達する手順がちょうど 2 通り存在するとき、組 (X, Y) を「良い組」と呼びます。 ただし、操作回数がともに L 回である 2 つの手順は、ある i \ (1 \leq i \leq L) に対して、i 回目の操作で移動する円盤・移動元・移動先の少なくとも 1 つが異なるとき、異なる手順とします。 特に、X = Y のとき、操作回数が最小の手順は空の操作手順のみの 1 通りであり、この場合は (X, Y) は「良い組」ではないありません。

ハノイの塔の状態は、1, 2, 3 からなる長さ N の文字列で表されます。 文字列の i 文字目が k であるとき、円盤 i が杭 k にあることを意味します。

1, 2, 3, ? からなる長さ N の文字列 A, B が与えられます。 A, B に含まれるすべての ? をそれぞれ独立に 1, 2, 3 のいずれかに置き換える方法は、? の総数を K とすると 3^K 通りあります。 そのうち、置き換えた後の文字列 A, B が表す状態をそれぞれ X, Y としたとき、(X, Y) が「良い組」となるような置き換え方の個数を 998244353 で割った余りを求めてください。

T 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

• 1 \leq T \leq 10^5
• 1 \leq N \leq 2 \times 10^5
• A, B は 1, 2, 3, ? からなる長さ N の文字列である
• すべてのテストケースについての N の総和は 2 \times 10^5 以下
• 入力される数値はすべて整数

入力例 1

5
2
12
2?
3
3?3
?3?
3
123
231
20
2?3?1?33?21?1???1?2?
?11?2?3?2?3??22?12??
50
??????????????????????????????????????????????????
??????????????????????????????????????????????????

出力例 1

1
4
0
1812
775062455

1 つ目のテストケースについて考えます。

置き換えた後の状態が (X,Y) = (12, 21) となったとき、X から Y へ到達する最小の操作回数は 3 回であり、そのような手順は以下の 2 通り存在します。

• 操作手順 1
  • 円盤 1 を杭 1 から杭 3 に移動する。
  • 円盤 2 を杭 2 から杭 1 に移動する。
  • 円盤 1 を杭 3 から杭 2 に移動する。
• 操作手順 2
  • 円盤 2 を杭 2 から杭 3 に移動する。
  • 円盤 1 を杭 1 から杭 2 に移動する。
  • 円盤 2 を杭 3 から杭 1 に移動する。

したがって、この場合 (X, Y) は良い組です。

置き換えた後の状態が (X, Y) = (12, 22) となったとき、X から Y へ到達する最小の操作回数は 1 回であり、そのような手順は以下の 1 通り存在します。

• 円盤 1 を杭 1 から杭 2 に移動する。

したがって、この場合 (X,Y) は良い組ではありません。

置き換えた後の状態が (X, Y) = (12, 23) となったとき、X から Y へ到達する最小の操作回数は 2 回であり、そのような手順は以下の 1 通り存在します。

• 円盤 2 を杭 2 から杭 3 に移動する。
• 円盤 1 を杭 1 から杭 2 に移動する。

したがって、この場合 (X, Y) は良い組ではありません。