小 Y là một sinh viên đại học, gần đây đang nghiên cứu các bài toán về chuỗi.

小 Y đã tìm hiểu các định nghĩa sau về chuỗi:

• Cho một chuỗi $s[1:n]$ có độ dài $n$, định nghĩa chuỗi con $s[l:r]$ ($1\le l\le r\le n$) là chuỗi mới thu được bằng cách chọn $s[l],s[l+1],\ldots,s[r]$ rồi nối chúng theo thứ tự.
• Cho một chuỗi $s[1:n]$ có độ dài $n$, định nghĩa kết quả đảo ngược $R(s)$ là chuỗi thu được bằng cách nối lần lượt $s[n],s[n-1],\ldots,s[1]$, tức là nối các ký tự của chuỗi theo thứ tự ngược lại.
• Cho hai chuỗi $a[1:n],b[1:n]$ cùng có độ dài $n$, định nghĩa $a$ nhỏ hơn $b$ theo thứ tự từ điển khi và chỉ khi tồn tại $1\le i\le n$ sao cho với mọi $1\le j<i$, $a[j]=b[j]$, và $a[i]<b[i]$.

Sau khi tìm hiểu các định nghĩa trên, 小 Y nghĩ ra bài toán sau:

Cho một chuỗi $s[1:n]$ có độ dài $n$. Có $q$ truy vấn, mỗi truy vấn cho hai tham số $i,r$. Bạn cần tìm có bao nhiêu giá trị $l$ thỏa mãn các điều kiện sau:

• $1\le l\le r$.
• $s[i:i+l-1]$ nhỏ hơn $R(s[i+l:i+2l-1])$ theo thứ tự từ điển.

小 Y muốn nhờ bạn giúp giải quyết bài toán này.

Dữ liệu vào

Đọc dữ liệu từ tệp string.in.

Bài này có nhiều bộ dữ liệu kiểm thử.

Dòng đầu tiên chứa hai số nguyên $c,t$, lần lượt biểu thị số hiệu bộ kiểm thử và số bộ dữ liệu kiểm thử. $c=0$ biểu thị bộ kiểm thử này là ví dụ.

Tiếp theo lần lượt nhập từng bộ dữ liệu kiểm thử. Với mỗi bộ dữ liệu:

Dòng đầu tiên chứa hai số nguyên dương $n,q$, biểu thị độ dài chuỗi và số truy vấn.

Dòng thứ hai chứa một chuỗi $s$ có độ dài $n$, chỉ gồm các chữ cái viết thường.

Trong $q$ dòng tiếp theo, mỗi dòng chứa hai số nguyên dương $i,r$, biểu thị một truy vấn; bảo đảm $i+2r-1\le n$.

Dữ liệu ra

Ghi kết quả vào tệp string.out.

Với mỗi truy vấn của mỗi bộ dữ liệu kiểm thử, in một dòng chứa một số nguyên, biểu thị số giá trị $l$ thỏa mãn điều kiện.

Ví dụ

Dữ liệu vào 1

0 2
9 3
abacababa
1 4
2 4
3 3
9 3
abaabaaba
1 4
2 4
3 3

Dữ liệu ra 1

4
0
3
2
0
2

Ghi chú

Với truy vấn đầu tiên của bộ dữ liệu thứ nhất:

• Khi $l=1$, $s[i:i+l-1]=\texttt{a}$, $R(s[i+l:i+l+l-1])=\texttt{b}$.
• Khi $l=2$, $s[i:i+l-1]=\texttt{ab}$, $R(s[i+l:i+l+l-1])=\texttt{ca}$.
• Khi $l=3$, $s[i:i+l-1]=\texttt{aba}$, $R(s[i+l:i+l+l-1])=\texttt{bac}$.
• Khi $l=4$, $s[i:i+l-1]=\texttt{abac}$, $R(s[i+l:i+l+l-1])=\texttt{baba}$.

Trong cả bốn trường hợp, $s[i:i+l-1]$ đều nhỏ hơn $R(s[i+l:i+2l-1])$ theo thứ tự từ điển, nên đáp án là $4$.

Ví dụ 2

Xem các tệp string/string2.in và string/string2.ans trong thư mục của thí sinh.

Phạm vi dữ liệu của ví dụ này thỏa mãn bộ kiểm thử $5$.

Ví dụ 3

Xem các tệp string/string3.in và string/string3.ans trong thư mục của thí sinh.

Ví dụ 4

Xem các tệp string/string4.in và string/string4.ans trong thư mục của thí sinh.

Phạm vi dữ liệu của ví dụ này thỏa mãn các bộ kiểm thử $24\sim 25$.

Giới hạn

Với mọi dữ liệu kiểm thử, bảo đảm: $1\le t\le 5$, $1\le n\le 10^5$, $1\le q\le 10^5$, $1\le i+2r-1\le n$, và chuỗi $s$ chỉ chứa chữ cái viết thường.

• Tính chất đặc biệt A: bảo đảm chuỗi chỉ chứa các ký tự a và b, và mỗi ký tự được chọn độc lập, với xác suất bằng nhau giữa a và b.
• Tính chất đặc biệt B: bảo đảm các ký tự kề nhau trong chuỗi đều khác nhau.