Loading [MathJax]/jax/output/HTML-CSS/fonts/TeX/fontdata.js

D. Frequency of String
time limit per test
1.5 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

You are given a string s. You should answer n queries. The i-th query consists of integer ki and string mi. The answer for this query is the minimum length of such a string t that t is a substring of s and mi has at least ki occurrences as a substring in t.

A substring of a string is a continuous segment of characters of the string.

It is guaranteed that for any two queries the strings mi from these queries are different.

Input

The first line contains string s (1|s|105).

The second line contains an integer n (1n105).

Each of next n lines contains an integer ki (1ki|s|) and a non-empty string mi — parameters of the query with number i, in this order.

All strings in input consists of lowercase English letters. Sum of length of all strings in input doesn't exceed 105. All mi are distinct.

Output

For each query output the answer for it in a separate line.

If a string mi occurs in s less that ki times, output -1.

Examples
Input
aaaaa
5
3 a
3 aa
2 aaa
3 aaaa
1 aaaaa
Output
3
4
4
-1
5
Input
abbb
7
4 b
1 ab
3 bb
1 abb
2 bbb
1 a
2 abbb
Output
-1
2
-1
3
-1
1
-1