#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
const int MAXCHAR = 26;
struct Vertex {
int next[MAXCHAR], go[MAXCHAR];
int leaf = -1;
int p = -1;
char pch;
int link = -1, leaflink = -1;
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);
get_link(trie[v].link);
trie[v].leaflink = (trie[trie[v].link].leaf != -1) ? trie[v].link : trie[trie[v].link].leaflink;
}
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];
}
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]);
get_link(v);
int cur = trie[v].leaf == -1 ? trie[v].leaflink : v;
while (cur != -1) {
results[trie[cur].leaf].push_back(i);
cur = trie[cur].leaflink;
}
}
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+Cgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKY29uc3QgaW50IE1BWE4gPSAxZTUgKyA1Owpjb25zdCBpbnQgTUFYQ0hBUiA9IDI2OwoKc3RydWN0IFZlcnRleCB7CiAgICBpbnQgbmV4dFtNQVhDSEFSXSwgZ29bTUFYQ0hBUl07CiAgICBpbnQgbGVhZiA9IC0xOwogICAgaW50IHAgPSAtMTsKICAgIGNoYXIgcGNoOwogICAgaW50IGxpbmsgPSAtMSwgbGVhZmxpbmsgPSAtMTsKCiAgICBWZXJ0ZXgoaW50IHAgPSAtMSwgY2hhciBjaCA9ICckJykgOiBwKHApLCBwY2goY2gpIHsKICAgICAgICBmaWxsKGJlZ2luKG5leHQpLCBlbmQobmV4dCksIC0xKTsKICAgICAgICBmaWxsKGJlZ2luKGdvKSwgZW5kKGdvKSwgLTEpOwogICAgfQp9OwoKdmVjdG9yPFZlcnRleD4gdHJpZSgxKTsKCnZvaWQgYWRkX3N0cmluZyhzdHJpbmcgY29uc3QgJnMsIGludCBpZHgpIHsKICAgIGludCB2ID0gMDsKICAgIGZvciAoY2hhciBjaCA6IHMpIHsKICAgICAgICBpbnQgYyA9IGNoIC0gJ2EnOwogICAgICAgIGlmICh0cmllW3ZdLm5leHRbY10gPT0gLTEpIHsKICAgICAgICAgICAgdHJpZVt2XS5uZXh0W2NdID0gdHJpZS5zaXplKCk7CiAgICAgICAgICAgIHRyaWUuZW1wbGFjZV9iYWNrKHYsIGNoKTsKICAgICAgICB9CiAgICAgICAgdiA9IHRyaWVbdl0ubmV4dFtjXTsKICAgIH0KICAgIHRyaWVbdl0ubGVhZiA9IGlkeDsKfQoKaW50IGdvKGludCB2LCBjaGFyIGNoKTsKCmludCBnZXRfbGluayhpbnQgdikgewogICAgaWYgKHRyaWVbdl0ubGluayA9PSAtMSkgewogICAgICAgIGlmICh2ID09IDAgfHwgdHJpZVt2XS5wID09IDApCiAgICAgICAgICAgIHRyaWVbdl0ubGluayA9IDA7CiAgICAgICAgZWxzZQogICAgICAgICAgICB0cmllW3ZdLmxpbmsgPSBnbyhnZXRfbGluayh0cmllW3ZdLnApLCB0cmllW3ZdLnBjaCk7CiAgICAgICAgZ2V0X2xpbmsodHJpZVt2XS5saW5rKTsKICAgICAgICB0cmllW3ZdLmxlYWZsaW5rID0gKHRyaWVbdHJpZVt2XS5saW5rXS5sZWFmICE9IC0xKSA/IHRyaWVbdl0ubGluayA6IHRyaWVbdHJpZVt2XS5saW5rXS5sZWFmbGluazsKICAgIH0KICAgIHJldHVybiB0cmllW3ZdLmxpbms7Cn0KCmludCBnbyhpbnQgdiwgY2hhciBjaCkgewogICAgaW50IGMgPSBjaCAtICdhJzsKICAgIGlmICh0cmllW3ZdLmdvW2NdID09IC0xKSB7CiAgICAgICAgaWYgKHRyaWVbdl0ubmV4dFtjXSAhPSAtMSkKICAgICAgICAgICAgdHJpZVt2XS5nb1tjXSA9IHRyaWVbdl0ubmV4dFtjXTsKICAgICAgICBlbHNlCiAgICAgICAgICAgIHRyaWVbdl0uZ29bY10gPSB2ID09IDAgPyAwIDogZ28oZ2V0X2xpbmsodiksIGNoKTsKICAgIH0KICAgIHJldHVybiB0cmllW3ZdLmdvW2NdOwp9CgpzdHJpbmcgUzsKaW50IE47CmludCBLW01BWE5dOwpzdHJpbmcgTVtNQVhOXTsKdmVjdG9yPGludD4gcmVzdWx0c1tNQVhOXTsKCmludCBtYWluKCkgewogICAgaW9zOjpzeW5jX3dpdGhfc3RkaW8oMCk7CiAgICBjaW4udGllKDApOwogICAgY2luID4+IFM7CiAgICBjaW4gPj4gTjsKICAgIGZvciAoaW50IGkgPSAwOyBpIDwgTjsgaSsrKSB7CiAgICAgICAgY2luID4+IEtbaV07CiAgICAgICAgY2luID4+IE1baV07CiAgICAgICAgYWRkX3N0cmluZyhNW2ldLCBpKTsKICAgIH0KCiAgICBpbnQgdiA9IDA7CiAgICBmb3IgKGludCBpID0gMDsgaSA8IFMuc2l6ZSgpOyBpKyspIHsKICAgICAgICB2ID0gZ28odiwgU1tpXSk7CiAgICAgICAgZ2V0X2xpbmsodik7CiAgICAgICAgaW50IGN1ciA9IHRyaWVbdl0ubGVhZiA9PSAtMSA/IHRyaWVbdl0ubGVhZmxpbmsgOiB2OwogICAgICAgIHdoaWxlIChjdXIgIT0gLTEpIHsKICAgICAgICAgICAgcmVzdWx0c1t0cmllW2N1cl0ubGVhZl0ucHVzaF9iYWNrKGkpOwogICAgICAgICAgICBjdXIgPSB0cmllW2N1cl0ubGVhZmxpbms7CiAgICAgICAgfQogICAgfQogICAgZm9yIChpbnQgaSA9IDA7IGkgPCBOOyBpKyspIHsKICAgICAgICBpbnQgbWluTGVuZ3RoID0gMSA8PCAzMDsKICAgICAgICBmb3IgKGludCBqID0gS1tpXTsgaiA8PSByZXN1bHRzW2ldLnNpemUoKTsgaisrKSB7CiAgICAgICAgICAgIG1pbkxlbmd0aCA9IG1pbihtaW5MZW5ndGgsIHJlc3VsdHNbaV1baiAtIDFdIC0gcmVzdWx0c1tpXVtqIC0gS1tpXV0pOwogICAgICAgIH0KICAgICAgICBpZiAobWluTGVuZ3RoID09IDEgPDwgMzApIHsKICAgICAgICAgICAgY291dCA8PCAtMSA8PCBlbmRsOwogICAgICAgIH0gZWxzZSB7CiAgICAgICAgICAgIGNvdXQgPDwgbWluTGVuZ3RoICsgTVtpXS5zaXplKCkgPDwgZW5kbDsKICAgICAgICB9CiAgICB9Cn0=