#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

const int N = 1007;
const int MOD = 1e9 + 7;
const double OO = 1e9;

ll myhash(string &str) {
    ll ans = 0;
    for (char i : str) {
        ans |= 1 << (i - 'a');
    }
    return ans;
}

ll myhash(int *arr) {
    ll ans = 0;
    for (int i = 0; i < 26; ++i) {
        if (arr[i])
            ans |= 1 << i;
    }
    return ans;
}

ll prep[N][N];
int n, q;
string str;

int hashed[26];

void pre() {
    for (int k = 1; k < n; ++k) {
        ll letters = 0;
        memset(hashed, 0, sizeof hashed);
        for (int i = 0; i < k - 1; ++i) {
            letters ^= (1 << (str[i] - 'a'));
            hashed[str[i] - 'a']++;
        }
        for (int en = k - 1; en < n; ++en) {
            letters ^= (1 << (str[en] - 'a'));
            hashed[str[en] - 'a']++;

            if (__builtin_popcount(letters) <= 1)
                prep[k][en] = myhash(hashed);
            else
                prep[k][en] = 0;

            letters ^= (1 << (str[en] - 'a'));
            hashed[str[en] - 'a']--;
        }
    }
}

int k;
string temp;

int main() {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "rt", stdin);
#else
    freopen("wcup.in", "rt", stdin);
#endif
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t;
    cin >> t;
    while (t--) {
        cin >> n >> q;
        cin >> str;
        pre();
        while (q--) {
            cin >> k;
            cin >> temp;
            ll h = myhash(temp);
            bool ok = 0;
            for (int en = k - 1; en < n; ++en) {
                if (prep[k][en] == h) {
                    cout << en << endl;
                    ok = 1;
                    break;
                }
            }
            cout << (ok ? "YES\n" : "NO\n");
        }
    }
    return 0;
}