문자열

Little Y는 문자열을 연구하는 대학생이다. Little Y는 다음 정의를 배웠다.

• 길이가 $n$인 문자열 $s[1:n]$에 대해, 부분 문자열 $s[l:r]$ ($1 \leq l \leq r \leq n$)은 $s[l], s[l+1], \dots, s[r]$을 순서대로 이어 붙인 문자열이다.
• 길이가 $n$인 문자열 $s[1:n]$에 대해, $R(s)$는 $s[n], s[n-1], \dots, s[1]$을 순서대로 이어 붙인 문자열이다. 원래 문자열을 뒤집은 것이다.
• 길이가 같은 두 문자열 $a[1:n]$, $b[1:n]$에 대해, $a$가 $b$보다 사전순으로 작다는 것은 모든 $1 \leq j < i$에 대해 $a[j] = b[j]$이고 $a[i] < b[i]$인 $1 \leq i \leq n$이 존재한다는 뜻이다.

문자열 $s[1:n]$이 주어지고 질의가 $q$개 주어진다. 각 질의는 정수 $i$와 $r$로 이루어진다. 각 질의마다 다음 두 조건을 모두 만족하는 $l$의 개수를 구하라.

• $1 \leq l \leq r$
• $s[i:i+l-1]$이 $R(s[i+l:i+2l-1])$보다 사전순으로 작다.

첫 줄에 두 정수 $c$와 $t$가 주어진다. $c$는 테스트 케이스 번호이고, $t$는 데이터 세트의 수이다. $c = 0$이면 예제 테스트이다.

각 데이터 세트는 다음과 같이 주어진다.

첫 줄에 문자열의 길이 $n$과 질의의 수 $q$가 주어진다.

둘째 줄에 길이 $n$의 소문자로만 이루어진 문자열 $s$가 주어진다.

이어서 $q$개의 줄에 질의 $i$와 $r$이 각각 주어진다. $i+2r-1 \leq n$이 보장된다.

각 데이터 세트의 각 질의마다 조건을 만족하는 $l$의 개수를 한 줄에 출력한다.

모든 테스트 데이터에 대해 $1 \leq t \leq 5$, $1 \leq n \leq 10^5$, $1 \leq q \leq 10^5$, $1 \leq i+2r-1 \leq n$이다. 문자열 $s$는 소문자로만 이루어진다.