Ильдар взял ленточку и покрасил её в несколько цветов. Формально, ленточка разбита на $$$n$$$ клеточек, каждую из которых он покрасил в один из $$$26$$$ цветов, которые можно обозначить строчными буквами латинского алфавита.
Ильдар решил, что он выберет отрезок ленточки $$$[l, r]$$$ ($$$1 \le l \le r \le n$$$), который ему нравится, и вырежет его из ленточки. Таким образом получится новая ленточка, которую можно условно представить как строку $$$t = s_l s_{l+1} \ldots s_r$$$.
Теперь Ильдар играет в следующую игру — разрезает ленточку $$$t$$$ на несколько новых ленточек и смотрит, сколько среди них различных. Формально, Ильдар выбирает $$$1 \le k \le |t|$$$ индекcов $$$1 \le i_1 < i_2 < \ldots < i_k = |t|$$$ и разрезает $$$t$$$ на $$$k$$$ ленточек-строк $$$t_1 t_2 \ldots t_{i_1}, t_{i_1 + 1} \ldots t_{i_2}, \ldots, {t_{i_{k-1} + 1}} \ldots t_{i_k}$$$ и считает среди них количество различных. Внезапно Ильдара заинтересовал вопрос — а какое минимальное количество различных как строк из них может получиться, при условии что среди этих кусочков хотя бы один вид ленточек повторяется хотя бы два раза? Результатом игры Ильдар считает это число. Если не существует ни одного способа разрезать $$$t$$$ таким образом, то результатом игры будет число -1.
К сожалению, Ильдар ещё не выбрал, какой именно отрезок ему нравится, но у него есть $$$q$$$ отрезков-предпочтений $$$[l_1, r_1]$$$, $$$[l_2, r_2]$$$, ..., $$$[l_q, r_q]$$$. Посчитайте для каждого из отрезков какой будет результат игры нём.
Первая строка входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 200\,000$$$) — длина изначальной ленточки у Ильдара.
Вторая строка содержит строку $$$s$$$, состоящую из $$$n$$$ строчных букв латинского алфавита — ленточка, которая есть у Ильдара.
Третья строка содержит одно целое число $$$q$$$ ($$$1 \le q \le 200\,000$$$) — количество отрезков-предпочтений у Ильдара.
Каждая из следующих $$$q$$$ строк содержит два целых числа $$$l_i$$$ и $$$r_i$$$ ($$$1 \le l_i \le r_i \le n$$$) — границы $$$i$$$-го отрезка.
Выведите $$$q$$$ строк, где $$$i$$$-я из них содержит результат игры на строке $$$[l_i, r_i]$$$.
9
abcabcdce
7
1 6
4 7
5 9
6 9
1 9
3 6
4 4
1
-1
4
3
2
2
-1
Рассмотрим первый пример.
Если Ильдар выберет отрезок $$$[1, 6]$$$, то он вырежет строку $$$t = abcabc$$$. Если разрезать $$$t$$$ на два кусочка $$$abc$$$ и $$$abc$$$, то строка $$$abc$$$ повторится два раза, а количество различных строк из разрезания будет равно $$$1$$$. Поэтому результат этой игры $$$1$$$.
Если Ильдар выберет отрезок $$$[4, 7]$$$, то он вырежет строку $$$t = abcd$$$. Эту строку невозможно разрезать на строки так, что будет хотя бы строка, повторяющаяся хотя бы два раза. Поэтому результат этой игры $$$-1$$$.
Если Ильдар выберет отрезок $$$[3, 6]$$$, то он вырежет строку $$$t = cabc$$$. Если разрезать $$$t$$$ на три кусочка $$$c$$$, $$$ab$$$ и $$$c$$$, то строка $$$c$$$ повторится два раза, а количество различных строк будет равно $$$2$$$. Поэтому результат этой игры $$$2$$$.
