#include <bits/stdc++.h>

using namespace std;

const int MaxN = (int)2e5 + 10;
const int INF = 1e9;

const int MaxL = 18;

char s[MaxN];
int n, q, en, eq, up[MaxN][MaxL];
int total[MaxN], pref[MaxN];

void solve() {
	scanf("%d%d\n", &n, &q);
	en += n;
	eq += q;
	assert (1 <= n && n <= 200000 && en <= 200000);
	assert (1 <= q && q <= 200000 && eq <= 200000);
	scanf("%s\n", s);
	assert (strlen(s) == n);
	for (int i = 1; i < n; ++i) {
		int j = pref[i - 1];
		while (j > 0 && s[i] != s[j]) {
			j = pref[j - 1];
		}
		pref[i] = j + (s[i] == s[j]);
	}
	for (int i = 0; i < n; ++i) {
		assert (s[i] >= 'a' && s[i] <= 'z');
		total[i + 1] = total[pref[i]] + 1;
		up[i + 1][0] = pref[i];
		for (int j = 1; j < MaxL; ++j) {
			up[i + 1][j] = up[up[i + 1][j - 1]][j - 1];
		}
	}
	for (int it = 1; it <= q; ++it) {
		int p, k;
		scanf("%d%d", &p, &k);
		assert (1 <= p && p <= n);
		assert (1 <= k && k <= n);
		if (total[p] < k) {
			printf("-1\n");
			continue;
		}
		k = total[p] - k;
		for (int i = MaxL - 1; i >= 0; --i) {
			if (k & (1 << i)) {
				p = up[p][i];
			}
		}
		printf("%d\n", p);
	}
	for (int i = 0; i <= n; ++i) {
		memset(up[i], 0, sizeof(up[i]));
		total[i] = pref[i] = 0;
	}
}

int main() {
//	freopen("input.txt", "r", stdin);
	int t;
	scanf("%d", &t);
	assert (1 <= t && t <= 100);
	while (t --> 0) {
		solve();
	}
	return 0;
}