409645: GYM103652 J Square Substrings

Bob has a string $$$s_{1} s_{2} \cdots s_{n}$$$ and $$$q$$$ queries $$$(l_i, r_i)$$$ ($$$i = 1, 2, \ldots, q$$$). For each query $$$(l_i, r_i)$$$, he would like to know the number of intervals $$$(L, R)$$$ such that $$$l_i \leq L \leq R \leq r_i$$$ and $$$s_{L} s_{L + 1} \cdots s_{R}$$$ is a square. Could you please help him?

A string $$$t_{1} t_{2} \cdots t_{m}$$$ is a square if and only if:

• $$$m$$$ is even;
• $$$t_i = t_{i + \frac{m}{2}}$$$ for $$$i = 1, 2, \ldots, \frac{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, $$$s_{1} s_{2} \cdots s_{n}$$$.

The $$$i$$$-th one of the following $$$q$$$ lines contains two integers $$$l_i$$$ and $$$r_i$$$, representing a query.

• $$$1 \leq T \leq 100$$$
• $$$1 \leq n, q \leq 10^6$$$
• $$$1 \leq l_i \leq r_i \leq n$$$
• The sum of $$$n$$$ in all test cases does not exceed $$$10^6$$$.
• The sum of $$$q$$$ in all test cases does not exceed $$$10^6$$$.

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
7 5
ababbab
1 4
2 5
3 6
4 7
1 7

Case #1:
1
1
1
1
3

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