제곱 부분 문자열

Bob에게 길이가 $n$인 문자열 $s_1s_2\cdots s_n$과 $q$개의 질의 $(l_i, r_i)$ ($i = 1, 2, \ldots, q$)가 있다. 각 질의 $(l_i, r_i)$에 대해, $l_i \le L \le R \le r_i$를 만족하고 $s_L s_{L+1} \cdots s_R$이 제곱 문자열인 구간 $(L, R)$의 개수를 구하라.

문자열 $t_1t_2\cdots t_m$이 제곱 문자열이려면 다음 두 조건을 모두 만족해야 하며, 이 조건을 만족할 때만 제곱 문자열이다.

• $m$은 짝수이다.
• $i = 1, 2, \ldots, m/2$에 대해 $t_i = t_{i+m/2}$이다.

입력에는 여러 테스트 케이스가 들어 있다. 첫 줄에 테스트 케이스의 수 $T$가 주어진다. 각 테스트 케이스는 다음과 같다.

첫 줄에 정수 $n$과 $q$가 주어진다. 둘째 줄에 길이 $n$의 소문자 문자열 $s_1s_2\cdots s_n$이 주어진다. 이어서 $q$개의 줄 중 $i$번째 줄에 질의를 나타내는 정수 $l_i$와 $r_i$가 주어진다.

각 테스트 케이스마다 먼저 "Case #x:" 줄을 출력한다. 여기서 $x$는 1부터 시작하는 테스트 케이스 번호다. 이후 각 질의의 답을 한 줄에 하나씩 출력한다.

$1 \le T \le 100$, $1 \le n, q \le 10^6$, $1 \le l_i \le r_i \le n$. 모든 테스트 케이스의 $n$ 합은 $10^6$을 넘지 않는다. 모든 테스트 케이스의 $q$ 합도 $10^6$을 넘지 않는다.

bb, abab, babbab는 제곱 문자열이지만 abba는 제곱 문자열이 아니다.