18658번 - Square Substrings 다국어

문제

Bob has a string s₁s₂ · · · s_n and q queries (l_i, r_i) (i = 1, 2, . . . , q). For each query (l_i, r_i), he would like to know the number of intervals (L, R) such that l_i ≤ L ≤ R ≤ r_i and s_Ls_L+1 · · · s_R is a square. Could you please help him?

A string t₁t₂ · · ·t_m is a square if and only if:

• m is even;
• t_i = t_i+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, s₁s₂ · · · s_n.

The i-th one of the following q lines contains two integers l_i and r_i, 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 ≤ 10⁶
• 1 ≤ l_i ≤ r_i ≤ n
• The sum of n in all test cases does not exceed 10⁶.
• The sum of q in all test cases does not exceed 10⁶.

힌트

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