시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
8 초 512 MB 0 0 0 0.000%

문제

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.

예제 입력 1

1
7 5
ababbab
1 4
2 5
3 6
4 7
1 7

예제 출력 1

Case #1:
1
1
1
1
3

힌트

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