题目描述

译自 POI 2012 Stage 2. Day 2「Okropny wiersz」

给定由小写英文字母组成的字符串 $S$，有 $q$ 个询问，每次询问给定 $S$ 的一个子串，求其最短循环节。

如果字符串 $A$ 可以由字符串 $B$ 重复若干次得到，则字符串 $B$ 是字符串 $A$ 的一个循环节。

输入格式

第一行一个正整数 $n (n \le 500\ 000)$，表示字符串 $S$ 的长度。

接下来一行 $n$ 个小写英文字母，表示字符串 $S$.

接下来一行一个正整数 $q (q \le 2\ 000\ 000)$，表示询问个数。

接下来 $q$ 行每行两个正整数 $a,b (1 \le a \le b \le n)$，表示询问字符串 $S$ 从第 $a$ 个字母到第 $b$ 个字母组成的子串的最短循环节长度。

输出格式

输出 $q$ 行，每行一个正整数，表示询问的答案。

样例

input

8
aaabcabc
3
1 3
3 8
4 8

output

1
3
5