끔찍한 시

Bytie는 어떤 시의 한 조각을 외워야 한다. 이 시는 현대 예술의 정신에 따라 소문자 알파벳으로만 이루어진 아주 긴 문자열이다. 듣기에는 형편없지만, 그건 Bytie의 가장 작은 걱정거리다. Bytie는 자신이 외워야 할 조각이 어느 것인지 완전히 잊어버렸고, 모든 조각이 외우기 어려워 보인다.

그래도 희망은 있다. 시의 어떤 부분들은 규칙적이기 때문이다. 때때로 어떤 조각 $A$는 다른 조각 $B$를 여러 번 이어 붙인 것과 같다. 즉, 어떤 정수 $k \ge 1$에 대해 $A = BB\cdots B = B^k$가 성립한다. 이때 $B$를 $A$의 완전한 주기(full period)라고 부른다. (특히, 모든 문자열은 자기 자신을 완전한 주기로 가진다.) 완전한 주기가 짧은 조각일수록 외우기 쉽다.

시 전체와 Bytie가 후보로 의심하는 조각들의 목록이 주어질 때, 각 조각에 대해 가장 짧은 완전한 주기의 길이를 구하라.

첫째 줄에 정수 $n$ ($1 \le n \le 500{,}000$)이 주어진다. 둘째 줄에는 소문자 알파벳으로 이루어진 길이 $n$의 문자열, 즉 시가 주어진다. 문자의 위치는 앞에서부터 $1$번부터 $n$번까지 번호를 매긴다.

다음 줄에는 조각의 개수를 나타내는 정수 $q$ ($1 \le q \le 2{,}000{,}000$)가 주어진다. 이어지는 $q$개의 줄에는 각각 두 정수 $a_i$와 $b_i$ ($1 \le a_i \le b_i \le n$)가 공백 하나로 구분되어 주어지며, 이는 위치 $a_i$에서 시작해 위치 $b_i$에서 끝나는 조각을 나타낸다.

$q$개의 줄을 출력한다. $i$번째 줄에는 $i$번째 조각의 가장 짧은 완전한 주기의 길이를 정수 하나로 출력한다.