1618 . 猴子打字機
Description
有一個定理是這樣的：讓一隻猴子在打字機上面隨意地打字，任何你想要的字串總有一天都會出現。
所以我們來做一點實驗吧，讓一隻猴子在鍵盤前面開始打字。不過這個鍵盤很特別，它支援複製與貼上的功能。隨著時代的演進，猴子們也越來越喜歡不定時地重複將某個子字串貼個幾次。
現在給你一個疑似是某隻猴子使用打字機所產生的字串 S，我們想知道的是，對於某些個子字串 S[a..b]，假設它是由某個原始字串完整地重覆接若干次，則請你找出最短的原始字串。例如 "abcabcabc" 的原始字串最短是 3，"bcabcabcab" 則是 10。
Input Format
輸入檔的第一行有一個正整數 T (T<=30) 表示測試資料的筆數。
對於每一組測試資料，第一行有一個正整數 N (1<=N<=500000)，表示字串 S 的長度。第二行有一個長度恰好為 N 的字串 S。第三行有一個整數 Q (0<=Q<=2000000)，第四行開始總共有 Q 行，每一行都有兩個正整數 a_i, b_i (1<=a_i<=b_i<=N)，表示我們關心的子字串。
Output Format
對於每一個詢問請回答這個子字串對應的最短原始字串長度。
Sample Input 1
1 8 aaabcabc 3 1 3 3 8 4 8
Sample Output 1
1 3 5
Hints
aaa由三個a接起來，abcabc由兩個abc接起來，bcabc則只能由一個bcabc表示。
Problem Source
Migrated from old NTUJ.
POI 19th Horrible Poem
Subtasks
| No. | Testdata Range | Score |
|---|