#include <bits/stdc++.h>
using namespace std;
const int N = 3e6 + 5;
int n, m, T, tot, tree[N][62], mp[N];

int Get(char x) {
	if (x >= 'A' && x <= 'Z')
		return x - 'A';
	else if (x >= 'a' && x <= 'z')
		return 26 + x - 'a';
	else
		return 52 + x - '0';
}

void insert(string s) {
	int u = 0;
	for (int i = 0; i < s.size(); i++) {
		int v = Get(s[i]);
		if (!tree[u][v])
			tree[u][v] = ++tot;
		u = tree[u][v];
		mp[u]++;
	}
}

int query(string s) {
	int u = 0;
	for (int i = 0; i < s.size(); i++) {
		int v = Get(s[i]);
		if (!tree[u][v])
			return 0;
		u = tree[u][v];
	}
	return mp[u];
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin >> T;
	while (T--) {
		for (int i = 0; i <= tot; i++) {
			for (int j = 0; j < 63; j++) {
				tree[i][j] = 0;
			}
			mp[i] = 0;
		}
		tot = 0;
		cin >> n >> m;
		for (int i = 1; i <= n; i++) {
			string t;
			cin >> t;
			insert(t);
		}
		for (int i = 1; i <= m; i++) {
			string t;
			cin >> t;
			cout << query(t) << endl;
		}
	}
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n, a[N], tree[N * 32][2], tot, ans;

void insert(int s) {
	int u = 0;
	for (int i = 30; i >= 0; i--) {
		int v = ((s >> i) & 1);
		if (tree[u][v] == 0)
			tree[u][v] = ++tot;
		u = tree[u][v];
	}
}

int query(int s) {
	int u = 0;
	int tmp = 0;
	for (int i = 30; i >= 0; i--) {
		int v = ((s >> i) & 1);
		if (tree[u][v ^ 1]) {
			u = tree[u][v ^ 1];
			tmp += (1 << i);
		} else
			u = tree[u][v];
	}
	return tmp;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	for (int i = 1; i <= n; i++)
		insert(a[i]);
	for (int i = 1; i <= n; i++)
		ans = max(ans, query(a[i]));
	cout << ans << endl;
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define ull unsigned long long
const int N = 105;
const ull base = 23333333;
int T, n, k, f[N][N], a[N];
ull h[N], p[N];

int Get(int l, int r) {
	return h[r] - h[l - 1] * p[r - l + 1];
}

int main() {
	cin >> T;
	while (T--) {
		cin >> n >> k;
		p[0] = 1;
		for (int i = 1; i <= n; i++) {
			cin >> a[i];
			h[i] = h[i - 1] * base + (ull)a[i];
			p[i] = p[i - 1] * base;
			f[i][i] = 1;
		}
		for (int len = 2; len <= n; len++) {
			for (int i = 1; i + len - 1 <= n; i++) {
				int j = i + len - 1;
				f[i][j] = 0x3f3f3f3f;
				for (int k = 1; k <= len; k++) {
					if (len % k == 0 && Get(i, j - k) == Get(i + k, j)) {
						f[i][j] = min(f[i][j], f[i][i + k - 1]);
					}
				}
				for (int k = i; k < j; k++) {
					f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j]);
				}
			}
		}
		if (f[1][n] <= k)
			cout << "YES\n";
		else
			cout << "NO\n";
	}
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define ll unsigned long long
const ll N = 105;
const ll Mod = 23333333;
string s;
ll n, f[N][N], p[N], h[N];

ll Get(ll l, ll r) {
	return h[r] - h[l - 1] * p[r - l + 1];
}

int main() {
	for (int i = 1; i <= 100; i++) {
		for (int j = 1; j <= 100; j++) {
			f[i][j] = 1e18;
			if (j - i + 1 >= 1)
				f[i][j] = j - i + 1;
		}
	}
	cin >> s;
	n = s.size();
	s = " " + s;
	p[0] = 1;
	for (int i = 1; i <= n; i++) {
		p[i] = p[i - 1] * Mod;
		h[i] = h[i - 1] * Mod + s[i];
		f[i][i] = 1;
	}
	for (int len = 2; len <= n; len++) {
		for (int i = 1, j = len; j <= n; i++, j++) {
			for (int k = 1; k <= len; k++) {
				if (len % k == 0) {
					if (Get(i, j - k) == Get(i + k, j)) {
						int tmp = len / k;
						int cnt = 0;
						while (tmp)
							cnt++, tmp /= 10;
						f[i][j] = min(f[i][j], cnt + 2 + f[i][i + k - 1]);
					}
				}
			}
			for (int k = i; k < j; k++) {
				f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j]);
			}
		}
	}
	cout << f[1][n] << endl;
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
int n, m, nxt[N];
string s, t;

int main() {
	cin >> s >> t;
	n = s.size(), m = t.size();
	nxt[0] = -1, nxt[1] = 0;
	int i = 2, j = 0;
	while (i <= m) {
		if (t[j] == t[i - 1])
			nxt[i] = j + 1, i++, j++;
		else if (nxt[j] != -1)
			j = nxt[j];
		else
			i++;
	}
	i = 0, j = 0;
	while (i < n) {
		if (s[i] == t[j])
			i++, j++;
		else if (nxt[j] != -1)
			j = nxt[j];
		else
			i++;
		if (j == m) {
			cout << i - m + 1 << endl;
			j = nxt[j];
		}
	}
	for (int i = 1; i <= m; i++) {
		cout << nxt[i] << " ";
	}
	return 0;
}