题目描述

Kewth 是 OI 游戏两开花的神仙。最近他在 T****p 上找到一个新奇的消消乐游戏。这款游戏的目标是，将一串有着黑白两种颜色的球消除到只剩下一个球。若剩下的球是白色的则会获得游戏的胜利。

每次消除操作可以简化成依次执行下面几个步骤：

1. 选择一段长度为正奇数的前缀 $S$。
2. 然后从后往前依次取出 $S$ 的最后三个球，根据这三个球的颜色将其变成一个黑色或者白色的球并放回去。重复此步骤直到只剩下一个球。
3. 将这个球放回到原来的序列前端。

其中，步骤二生成的球的颜色的确定规则会在每个关卡开始的时候给定。

现在这个消消乐开了夏活，活动关卡中，会在一些位置上放置“混沌球”，在你开始进行消除操作之前，你需要给每一个“混沌球”染上黑色或者白色。

Kewth 是一个善于思考的神，于是他就想，能不能算出有多少种给“混沌球”染色的方案，使得局面是可以获胜的？

打开了关卡后，Kewth 在 $10^{-100}s$ 内就计算出了答案。为了证明你不比 Kewth 菜 $10^{100}$ 倍，你需要在 $1s$ 内计算出结果。

Kewth 知道凡人不希望计算过大的数字，于是你只需要告诉他你的答案对 $998244353$ 取模的结果就行了。

输入格式

从 game.in 中读入。

第一行一个正整数 $T$，表示 Kewth 需要你计算一共 $T$ 个关卡。

接下来 $T$ 组关卡信息。这里我们使用 $0$ 表示颜色为黑色的球，$1$ 表示颜色为白色的球。每组关卡信息的第一行是一个长度为 $8$ 的 01 串，其中第 $i$ 个字符表示当从后往前取出的三个字符依次排列为 $i$ 的二进制表示（如，00001 进行一次步骤 $2$，取出的依次为 $1,0,0$，对应的 $i$ 即为 $4$）时，放回去的球是黑色还是白色。第二行是一个长度为 $n$ 的仅包含 01? 的字符串，表示当前关卡中黑球、白球、混沌球的排列顺序，保证 $n$ 为奇数。

输出格式

输出到 game.out 中。

对于每一个关卡，你都需要告诉 Kewth 你认为能获胜的局面数模 $998244353$ 的结果。

具体的，输出共 $T$ 行，每行一个非负整数，表示答案对 $998244353$ 取模的结果。

样例

样例 1

1
10001100
0000001

1

注意到有且仅有一种可能的给所有混沌球染色的方案。那么仅考虑这个情况，我们可以先选择一个长度为 $5$ 的前缀 $00000$，将其消除：$00000\to001\to1$，然后将 $1$ 放回得到 $101$。再进行一次消除即可得到 $1$。

样例 2

1
11100111
???

6

样例 3、4

见附加文件中 game*.in 与 game*.ans。

数据范围

对于所有数据，保证 $1\le T\le 10$，$1\le n\le 10^5$ 且 $n$ 为奇数。

数据点编号	$n\le$	特殊性质
$1,2,3$	$2\times 10^3$	无
$4,5,6,7$		$\text{A}$
$8,9,10,11$		$\text{B}$
$12,13,14,15$	$10^5$	$\text{A}$
$16,17,18,19$		$\text{B}$
		无

特殊性质 $\text{A}$：保证初始游戏局面不存在 ?。

特殊性质 $\text{B}$：保证消除规则为 00010111。