#include<bits/stdc++.h>
using namespace std;

#define QwQ330AwA return 0
#define ll long long

const int mod = 998244353;
const int N = 100005;
const int M = 330;
int f[2][M];
int to[M][2];
int mask[8];
bool vis[22][1 << 21], g[22][1 << 21];
bool tmp[22];
struct Node {
	int s;
	int len;
} pos[M];
int cnt;

bool dfs(int len, int s) {
	if (len == 1) return s;
	if (vis[len][s]) return g[len][s];
	vis[len][s] = 1;
	for (int i = 0; i <= len - 3; i++) {
		int w = (mask[(s >> i) & 7] << i) | (s & ((1 << i) - 1)) | ((s >> (i + 3)) << (i + 1));
		if (dfs(len - 2, w)) return g[len][s] = 1;
	}
	return g[len][s] = 0;
}

bool check(Node u, Node v) {
	int su = u.s, lenu = u.len;
	int sv = v.s, lenv = v.len;
	if (lenu % 2 != lenv % 2) return 0;
	for (int i = 0; i <= max(lenu, lenv) + 10; i++) {
		if (!tmp[i]) {
			tmp[i] = 1;
			for (int s = 0; s < (1 << i); s++) vis[i][s] = 0;
		}
	}
	for (int i = (lenu & 1) ^ 1; i <= 10; i += 2) {
		for (int s = 0; s < (1 << i); s++) {
			if (dfs(lenu + i, su | (s << lenu)) != dfs(lenv + i, sv | (s <<lenv))) return 0;
		}
	}
	return 1;
}

void build() {
	memset(tmp, 0, sizeof(tmp));
	queue <int> q;
	cnt = 0;
	pos[++cnt] = {0, 0};
	q.push(1);
	while (!q.empty()) {
		int u = q.front();
		q.pop();
		int flag = 0;
		Node nw = {pos[u].s, pos[u].len + 1};
		for (int i = 1; i <= cnt; i++) {
			if (check(nw, pos[i])) {
				to[u][0] = i;
				flag = 1;
				break;
			}
		}
		if (!flag) {
			cnt++;
			pos[cnt] = nw;
			to[u][0] = cnt;
			q.push(cnt);
		}
		flag = 0;
		nw = {pos[u].s | (1 << pos[u].len), pos[u].len + 1};
		for (int i = 1; i <= cnt; i++) {
			if (check(nw, pos[i])) {
				to[u][1] = i;
				flag = 1;
				break;
			}
		}
		if (!flag) {
			cnt++;
			pos[cnt] = nw;
			to[u][1] = cnt;
			q.push(cnt);
		}
	}
}

void add(int &x, int y) {
	x += y;
	if (x >= mod) x -= mod;
}

void solve() {
	string s;
	cin >> s;
	for (int i = 0; i < 8; i++) mask[i] = s[i] - '0';
	string t;
	cin >> t;
	int n = t.length();
	build();
//	cout << cnt << '\n';
	memset(f[0], 0, sizeof(f[0]));
	f[0][1] = 1;
	for (int i = 0; i < n; i++) {
		int op = i & 1;
		for (int j = 1; j <= cnt; j++) f[op ^ 1][j] = 0;
		for (int j = 1; j <= cnt; j++) {
			if (t[i] != '0') add(f[op ^ 1][to[j][1]], f[op][j]);
			if (t[i] != '1') add(f[op ^ 1][to[j][0]], f[op][j]);
		}
	}
	int op = n & 1;
	int ans = 0;
	for (int i = 1; i <= cnt; i++) {
		if (pos[i].len % 2 == 1 && dfs(pos[i].len, pos[i].s)) add(ans, f[op][i]);
	}
	cout << ans << '\n';
}

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int t;
	cin >> t;
	while (t--) solve();
	QwQ330AwA;
}