#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
const int MAXCHAR = 26;
struct Vertex {
int next[MAXCHAR];
int leaf = -1;
int p = -1;
char pch;
int link = -1;
int leaflink = -1;
int go[MAXCHAR];
Vertex(int p = -1, char ch = '$') : p(p), pch(ch) {
fill(begin(next), end(next), -1);
fill(begin(go), end(go), -1);
}
};
vector<Vertex> trie(1);
void add_string(string const &s, int idx) {
int v = 0;
for (char ch : s) {
int c = ch - 'a';
if (trie[v].next[c] == -1) {
trie[v].next[c] = trie.size();
trie.emplace_back(v, ch);
}
v = trie[v].next[c];
}
trie[v].leaf = idx;
}
int go(int v, char ch);
int get_link(int v) {
if (trie[v].link == -1) {
if (v == 0 || trie[v].p == 0)
trie[v].link = 0;
else
trie[v].link = go(get_link(trie[v].p), trie[v].pch);
}
return trie[v].link;
}
int go(int v, char ch) {
int c = ch - 'a';
if (trie[v].go[c] == -1) {
if (trie[v].next[c] != -1)
trie[v].go[c] = trie[v].next[c];
else
trie[v].go[c] = v == 0 ? 0 : go(get_link(v), ch);
}
return trie[v].go[c];
}
int getleaf(int i) {
if (trie[i].leaflink != -1) {
return trie[i].leaflink;
}
int nxt = get_link(i);
if (nxt > 0) {
if (trie[nxt].leaf != -1) {
trie[i].leaflink = nxt;
} else {
trie[i].leaflink = getleaf(nxt);
}
return trie[i].leaflink;
}
return 0;
}
string S;
int N;
int K[MAXN];
string M[MAXN];
vector<int> results[MAXN];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> S;
cin >> N;
for (int i = 0; i < N; i++) {
cin >> K[i];
cin >> M[i];
add_string(M[i], i);
}
int v = 0;
for (int i = 0; i < S.size(); i++) {
v = go(v, S[i]);
int cur = v;
while (getleaf(cur) > 0) {
cur = getleaf(cur);
results[trie[cur].leaf].push_back(i);
}
if (trie[v].leaf != -1) {
results[trie[v].leaf].push_back(i);
}
}
for (int i = 0; i < N; i++) {
int minLength = 1 << 30;
for (int j = K[i]; j <= results[i].size(); j++) {
minLength = min(minLength, results[i][j - 1] - results[i][j - K[i]]);
}
if (minLength == 1 << 30) {
cout << -1 << endl;
} else {
cout << minLength + M[i].size() << endl;
}
}
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+Cgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKY29uc3QgaW50IE1BWE4gPSAxZTUgKyA1Owpjb25zdCBpbnQgTUFYQ0hBUiA9IDI2OwoKc3RydWN0IFZlcnRleCB7CiAgICBpbnQgbmV4dFtNQVhDSEFSXTsKICAgIGludCBsZWFmID0gLTE7CiAgICBpbnQgcCA9IC0xOwogICAgY2hhciBwY2g7CiAgICBpbnQgbGluayA9IC0xOwogICAgaW50IGxlYWZsaW5rID0gLTE7CiAgICBpbnQgZ29bTUFYQ0hBUl07CgogICAgVmVydGV4KGludCBwID0gLTEsIGNoYXIgY2ggPSAnJCcpIDogcChwKSwgcGNoKGNoKSB7CiAgICAgICAgZmlsbChiZWdpbihuZXh0KSwgZW5kKG5leHQpLCAtMSk7CiAgICAgICAgZmlsbChiZWdpbihnbyksIGVuZChnbyksIC0xKTsKICAgIH0KfTsKCnZlY3RvcjxWZXJ0ZXg+IHRyaWUoMSk7Cgp2b2lkIGFkZF9zdHJpbmcoc3RyaW5nIGNvbnN0ICZzLCBpbnQgaWR4KSB7CiAgICBpbnQgdiA9IDA7CiAgICBmb3IgKGNoYXIgY2ggOiBzKSB7CiAgICAgICAgaW50IGMgPSBjaCAtICdhJzsKICAgICAgICBpZiAodHJpZVt2XS5uZXh0W2NdID09IC0xKSB7CiAgICAgICAgICAgIHRyaWVbdl0ubmV4dFtjXSA9IHRyaWUuc2l6ZSgpOwogICAgICAgICAgICB0cmllLmVtcGxhY2VfYmFjayh2LCBjaCk7CiAgICAgICAgfQogICAgICAgIHYgPSB0cmllW3ZdLm5leHRbY107CiAgICB9CiAgICB0cmllW3ZdLmxlYWYgPSBpZHg7Cn0KCmludCBnbyhpbnQgdiwgY2hhciBjaCk7CgppbnQgZ2V0X2xpbmsoaW50IHYpIHsKICAgIGlmICh0cmllW3ZdLmxpbmsgPT0gLTEpIHsKICAgICAgICBpZiAodiA9PSAwIHx8IHRyaWVbdl0ucCA9PSAwKQogICAgICAgICAgICB0cmllW3ZdLmxpbmsgPSAwOwogICAgICAgIGVsc2UKICAgICAgICAgICAgdHJpZVt2XS5saW5rID0gZ28oZ2V0X2xpbmsodHJpZVt2XS5wKSwgdHJpZVt2XS5wY2gpOwogICAgfQogICAgcmV0dXJuIHRyaWVbdl0ubGluazsKfQoKaW50IGdvKGludCB2LCBjaGFyIGNoKSB7CiAgICBpbnQgYyA9IGNoIC0gJ2EnOwogICAgaWYgKHRyaWVbdl0uZ29bY10gPT0gLTEpIHsKICAgICAgICBpZiAodHJpZVt2XS5uZXh0W2NdICE9IC0xKQogICAgICAgICAgICB0cmllW3ZdLmdvW2NdID0gdHJpZVt2XS5uZXh0W2NdOwogICAgICAgIGVsc2UKICAgICAgICAgICAgdHJpZVt2XS5nb1tjXSA9IHYgPT0gMCA/IDAgOiBnbyhnZXRfbGluayh2KSwgY2gpOwogICAgfQogICAgcmV0dXJuIHRyaWVbdl0uZ29bY107Cn0KCmludCBnZXRsZWFmKGludCBpKSB7CiAgICBpZiAodHJpZVtpXS5sZWFmbGluayAhPSAtMSkgewogICAgICAgIHJldHVybiB0cmllW2ldLmxlYWZsaW5rOwogICAgfQogICAgaW50IG54dCA9IGdldF9saW5rKGkpOwogICAgaWYgKG54dCA+IDApIHsKICAgICAgICBpZiAodHJpZVtueHRdLmxlYWYgIT0gLTEpIHsKICAgICAgICAgICAgdHJpZVtpXS5sZWFmbGluayA9IG54dDsKICAgICAgICB9IGVsc2UgewogICAgICAgICAgICB0cmllW2ldLmxlYWZsaW5rID0gZ2V0bGVhZihueHQpOwogICAgICAgIH0KICAgICAgICByZXR1cm4gdHJpZVtpXS5sZWFmbGluazsKICAgIH0KICAgIHJldHVybiAwOwp9CgpzdHJpbmcgUzsKaW50IE47CmludCBLW01BWE5dOwpzdHJpbmcgTVtNQVhOXTsKdmVjdG9yPGludD4gcmVzdWx0c1tNQVhOXTsKCmludCBtYWluKCkgewogICAgaW9zOjpzeW5jX3dpdGhfc3RkaW8oMCk7CiAgICBjaW4udGllKDApOwogICAgY2luID4+IFM7CiAgICBjaW4gPj4gTjsKICAgIGZvciAoaW50IGkgPSAwOyBpIDwgTjsgaSsrKSB7CiAgICAgICAgY2luID4+IEtbaV07CiAgICAgICAgY2luID4+IE1baV07CiAgICAgICAgYWRkX3N0cmluZyhNW2ldLCBpKTsKICAgIH0KCiAgICBpbnQgdiA9IDA7CiAgICBmb3IgKGludCBpID0gMDsgaSA8IFMuc2l6ZSgpOyBpKyspIHsKICAgICAgICB2ID0gZ28odiwgU1tpXSk7CiAgICAgICAgaW50IGN1ciA9IHY7CiAgICAgICAgd2hpbGUgKGdldGxlYWYoY3VyKSA+IDApIHsKICAgICAgICAgICAgY3VyID0gZ2V0bGVhZihjdXIpOwogICAgICAgICAgICByZXN1bHRzW3RyaWVbY3VyXS5sZWFmXS5wdXNoX2JhY2soaSk7CiAgICAgICAgfQogICAgICAgIGlmICh0cmllW3ZdLmxlYWYgIT0gLTEpIHsKICAgICAgICAgICAgcmVzdWx0c1t0cmllW3ZdLmxlYWZdLnB1c2hfYmFjayhpKTsKICAgICAgICB9CiAgICB9CiAgICBmb3IgKGludCBpID0gMDsgaSA8IE47IGkrKykgewogICAgICAgIGludCBtaW5MZW5ndGggPSAxIDw8IDMwOwogICAgICAgIGZvciAoaW50IGogPSBLW2ldOyBqIDw9IHJlc3VsdHNbaV0uc2l6ZSgpOyBqKyspIHsKICAgICAgICAgICAgbWluTGVuZ3RoID0gbWluKG1pbkxlbmd0aCwgcmVzdWx0c1tpXVtqIC0gMV0gLSByZXN1bHRzW2ldW2ogLSBLW2ldXSk7CiAgICAgICAgfQogICAgICAgIGlmIChtaW5MZW5ndGggPT0gMSA8PCAzMCkgewogICAgICAgICAgICBjb3V0IDw8IC0xIDw8IGVuZGw7CiAgICAgICAgfSBlbHNlIHsKICAgICAgICAgICAgY291dCA8PCBtaW5MZW5ndGggKyBNW2ldLnNpemUoKSA8PCBlbmRsOwogICAgICAgIH0KICAgIH0KfQ==