Square Substrings

Bob has a string s1s2 · · · sn and q queries (li, ri) (i = 1, 2, . . . , q). For each query (li, ri), he would like to know the number of intervals (L, R) such that li ≤ L ≤ R ≤ ri and sLsL+1 · · · sR is a square. Could you please help him?

A string t1t2 · · ·tm is a square if and only if:

• m is even;
• ti = ti+m/2 for i = 1, 2, . . . , m/2.

The input contains several test cases. The first line contains an integer T indicating the number of test cases. The following describes all test cases. For each test case:

The first line contains two integers n and q.

The second line contains a string of n lowercase letters, s1s2 · · · sn.

The i-th one of the following q lines contains two integers li and ri, representing a query.

For each test case, firstly output a line containing “Case #x:” (without quotes), where x is the test case number starting from 1.

Then, for each query, output a line containing an integer, denoting the answer to this query.

• 1 ≤ T ≤ 100
• 1 ≤ n, q ≤ 106
• 1 ≤ li ≤ ri ≤ n
• The sum of n in all test cases does not exceed 106.
• The sum of q in all test cases does not exceed 106.

bb, abab and babbab are squares, while abba is not a square.