Problem Description
For a string S=s1s2⋯sN, the period of S is defined as the smallest positive integer p <= N, such that si+p = si holds for all 1 <= i <= N – p. Now given two integers L and R (1 <= L <= R <= N), you are asked to find out the period of sLsL+1⋯sR.
Input
The input begins with an integer T (T <= 20), indicating the number of test case. The first line of each case contains a string S, which consists of N (1 <= N <= 100000) lowercase English letters. The second line contains an integer Q (1 <= N <= 100000), indicating the number of queries. The following Q lines each contain two integers L and R (1 <= L <= R <= N).
The total length of all the strings is not larger than 500000, and the total number of queries is not larger than 200000.
Output
For each case, output "Case #X:" in a line where X is the case number, staring from 1. Then for each query, output the answer in a line.
Sample Input
2
aaabaa
3
1 3
1 4
2 5
abcabcabc
1
1 9
Sample Output
Case #1:
1
4
3
Case #2:
3
