Y kecil adalah seorang mahasiswa yang belakangan ini meneliti persoalan tentang string.

Y kecil mempelajari definisi-definisi berikut tentang string:

• Diberikan sebuah string $s[1:n]$ dengan panjang $n$. Substring $s[l:r]$ ($1\le l\le r\le n$) didefinisikan sebagai string baru yang diperoleh dengan memilih $s[l],s[l+1],\ldots,s[r]$ lalu menggabungkannya secara berurutan.
• Diberikan sebuah string $s[1:n]$ dengan panjang $n$. Hasil pembalikannya, $R(s)$, didefinisikan sebagai penggabungan $s[n],s[n-1],\ldots,s[1]$ secara berurutan, yaitu string yang diperoleh dengan menggabungkan karakter string tersebut dalam urutan terbalik.
• Diberikan dua string $a[1:n],b[1:n]$ yang masing-masing panjangnya $n$. Urutan leksikografis $a$ didefinisikan lebih kecil daripada $b$ jika dan hanya jika terdapat $1\le i\le n$ sehingga untuk setiap $1\le j<i$, berlaku $a[j]=b[j]$, dan $a[i]<b[i]$.

Setelah mempelajari definisi di atas, Y kecil memikirkan persoalan berikut:

Diberikan sebuah string $s[1:n]$ dengan panjang $n$. Terdapat $q$ pertanyaan, masing-masing memberikan dua parameter $i,r$. Kamu harus menentukan banyaknya $l$ yang memenuhi kondisi berikut:

• $1\le l\le r$.
• Urutan leksikografis $s[i:i+l-1]$ lebih kecil daripada $R(s[i+l:i+2l-1])$.

Y kecil ingin meminta bantuanmu untuk menyelesaikan persoalan ini.

Masukan

Baca data dari berkas string.in.

Soal ini memiliki beberapa kasus uji.

Baris pertama masukan berisi dua bilangan bulat $c,t$, yang berturut-turut menyatakan nomor pengujian dan banyaknya kasus uji. Nilai $c=0$ menyatakan bahwa pengujian tersebut merupakan contoh.

Berikutnya diberikan setiap kasus uji secara berurutan. Untuk setiap kasus uji:

Baris pertama masukan berisi dua bilangan bulat positif $n,q$, yang menyatakan panjang string dan banyaknya pertanyaan.

Baris kedua masukan berisi sebuah string $s$ dengan panjang $n$ yang hanya terdiri dari huruf kecil.

Masing-masing dari $q$ baris masukan berikutnya berisi dua bilangan bulat positif $i,r$ yang menyatakan sebuah pertanyaan. Dijamin $i+2r-1\le n$.

Keluaran

Tulis keluaran ke berkas string.out.

Untuk setiap pertanyaan pada setiap kasus uji, keluarkan satu baris berisi sebuah bilangan bulat yang menyatakan banyaknya $l$ yang memenuhi kondisi.

Contoh

Masukan 1

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

Keluaran 1

4
0
3
2
0
2

Penjelasan

Untuk pertanyaan pertama pada kasus uji pertama:

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

Dalam keempat keadaan tersebut, urutan leksikografis $s[i:i+l-1]$ selalu lebih kecil daripada $R(s[i+l:i+2l-1])$, sehingga jawabannya adalah $4$.

Contoh 2

Lihat string/string2.in dan string/string2.ans dalam direktori peserta.

Batasan data contoh ini memenuhi batasan pengujian ke-5.

Contoh 3

Lihat string/string3.in dan string/string3.ans dalam direktori peserta.

Contoh 4

Lihat string/string4.in dan string/string4.ans dalam direktori peserta.

Batasan data contoh ini memenuhi batasan pengujian $24\sim 25$.

Batasan

Untuk semua data uji, dijamin: $1\le t\le 5$, $1\le n\le 10^5$, $1\le q\le 10^5$, $1\le i+2r-1\le n$, dan string $s$ hanya terdiri dari huruf kecil.

• Sifat khusus A: dijamin bahwa string hanya terdiri dari karakter a dan b, dan setiap karakter dipilih secara independen dengan peluang yang sama dari a dan b.
• Sifat khusus B: dijamin bahwa karakter-karakter yang bersebelahan dalam string saling berbeda.