D. Matchmaker
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are playing Matchmaker, in this version of the game, two people are considered a match made in heaven only if both have everything in similar.

Once a match is made, those people cannot partipate in other matches (of course)

You are playing this game on a string. So two letters exactly equal can be considered as a match. But being a good matchmaker, you want the number of matches to be as much as possible. Hence you can perform one type of operation on the string

  • Choose any index $$$i$$$ and replace it with a lowercase letter of your choice.

Since this task is very easy, you need to perform this on a particular substring of the string

You are given a string $$$s$$$ and $$$q$$$ queries to be answered on the string. For each query l, r you need to find that how many (minimum) characters between s[l], s[l + 1], s[l + 2].....s[r] must be changed such that you can create maximum number of matches between s[l], s[l + 1], s[l + 2].....s[r]

Input

The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 500$$$) — the number of testcases

  • The first line contains two integers, $$$n$$$ ($$$1 \le n \le 10^5$$$) and $$$q$$$ ($$$1 \le q \le 10^5$$$), where $$$n$$$ is the number of letters in the string and $$$q$$$ is the number of queries to be answered
  • The second line contains the string
  • $$$n$$$ lines follow, each containing 2 numbers $$$l$$$ and $$$r$$$, the substring on which the query is to be answered ($$$1 \le l, r \le n$$$)

It is guaranteed that sum of all $$$n + q$$$ among tests do not exceed $$$2 * 10^5$$$

Output

For each test, print the answer of each query

Example
Input
2
6 4
abcdef
1 6
2 2
3 6
1 4
6 3
aaabbb
1 3
4 6
1 6
Output
3
0
2
2
0
0
1