Дана строка \(s\). Требуется ответить на \(n\) запросов. \(i\)-й запрос состоит из целого числа \(k_i\) и строки \(m_i\), ответом является минимальная длина строки \(t\) такой, что \(t\) является подстрокой \(s\) и строка \(m_i\) входит в \(t\) как подстрока не менее \(k_i\) раз.
Подстрокой строки называется любая последовательность подряд идущих символов в этой строке.
Гарантируется, что для любых двух запросов строки \(m_i\) из этих запросов различны.
Выходные данные
Для каждого запроса выведите ответ на него в отдельной строке.
Если строка \(m_{i}\) встречается в \(s\) менее \(k_{i}\) раз, выведите -1.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
aaaaa
5
3 a
3 aa
2 aaa
3 aaaa
1 aaaaa
|
3
4
4
-1
5
|
|
2
|
abbb
7
4 b
1 ab
3 bb
1 abb
2 bbb
1 a
2 abbb
|
-1
2
-1
3
-1
1
-1
|