|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|8 초||512 MB||24||21||2||50.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:
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 7 5 ababbab 1 4 2 5 3 6 4 7 1 7
Case #1: 1 1 1 1 3
babbab are squares, while
abba is not a square.