5814：Find the Period

For a string $S = s_{1}s_{2}\cdots s_{N}$, 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 $s_{L}s_{L+1}\cdots s_{R}$.

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.

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.