Problem Description

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}$.

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.

2
aaabaa
3
1 3
1 4
2 5
abcabcabc
1
1 9

Case #1:
1
4
3
Case #2:
3

Author

SYSU