시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
8 초 | 512 MB | 31 | 22 | 3 | 27.273% |
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
bb
, abab
and babbab
are squares, while abba
is not a square.