給出一個(gè)由小寫英文字母組成的字符串 S，再給出 q 個(gè)詢問，要求回答 S 某個(gè)子串的最短循環(huán)節(jié)。

如果字符串 B 是字符串 A 的循環(huán)節(jié)，那么 A 可以由 B 重復(fù)若干次得到。

第一行一個(gè)正整數(shù) n，表示 S 的長(zhǎng)度。

第二行 n 個(gè)小寫英文字母，表示字符串 S 。

第三行一個(gè)正整數(shù) q ，表示詢問個(gè)數(shù)。

下面 q 行每行兩個(gè)正整數(shù) a,b，表示詢問字符串 S[a..b] 的最短循環(huán)節(jié)長(zhǎng)度。

8
aaabcabc
3
1 3
3 8
4 8

1
3
5