#include <bits/stdc++.h>

typedef unsigned long long ull;
typedef long long ll;

char s[19];
int trans[1 << 18][2][2];

int len;
ull ans[1 << 18], cur[1 << 18];

std::pair<unsigned, unsigned> rec(ull n, ll l, ll r) {
	if (!n) {
		memset(cur, 0, sizeof(ull) << len);
		for (int i = l + 1; i <= r; ++i) cur[1 << (len - i - 1)] = 1;
		return std::make_pair(1 << (len - l - 1), 1 << (len - r - 1));
	}
	unsigned x, y;
	std::tie(x, y) = rec(n >> 1, l >> 1, r >> 1);
	int b = n & 1;
	static ull tmp[1 << 18];
	memcpy(tmp, cur, sizeof(ull) << len); memset(cur, 0, sizeof(ull) << len);
	for (int i = 0; i != 1 << len; ++i) {
		cur[trans[i][b][0]] += tmp[i];
		cur[trans[i][b][1]] += tmp[i];
	}
	if (r & 1) y = trans[y][b][1];
	else { --cur[trans[y][b][1]]; y = trans[y][b][0]; }
	if (l & 1) x = trans[x][b][1];
	else { ++cur[trans[x][b][1]]; x = trans[x][b][0]; }
	return std::make_pair(x, y);
}

int main() {
	int T; std::cin >> T;
	while (T--) {
		int n, K; ull m, L, R; std::cin >> n >> m >> K >> L >> R >> s;
		unsigned poly = 0;
		for (int i = 0; i <= n; ++i) if (s[i] == '1') poly |= 1U << i;
		--L; --R;
		len = std::max(n, K);
		for (unsigned i = 0; i != 1 << len; ++i) {
			ull db = 0;
			for (int j = 0; j != len; ++j) if ((i >> j) & 1)
				db |= 1ULL << (j * 2);
			trans[i][0][0] = db >> (len - 1); trans[i][0][1] = db >> len;
			ull conv = 0;
			for (int j = 0; j <= len; ++j) if ((poly >> j) & 1)
				conv ^= db << j;
			trans[i][1][0] = (conv >> (len - 1)) & ((1U << len) - 1);
			trans[i][1][1] = (conv >> len) & ((1U << len) - 1);
		}
		memset(ans, 0, sizeof(ull) << K);
		if (R - L + 1 >= K) {
			rec(m, L + K - 2, R);
			for (int i = 0; i != 1 << len; ++i) ans[i >> (len - K)] += cur[i];
		}
		std::cin >> s;
		unsigned str = 0;
		for (int i = 0; i != K; ++i) if (s[i] == '1') str |= 1U << i;
		std::cout << ans[str] << '\n';
	}

	return 0;
}