Ильдар взял ленточку и покрасил её в несколько цветов. Формально, ленточка разбита на $$$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]$$$. Посчитайте для каждого из отрезков какой будет результат игры нём.