Kirito: "Can you tell me whether string s is a palindrome or not?"
You: "Sure, it is too easy."
Kirito: "Can you tell me how many substrings of s are palindromes?"
You: "Sure, it is easy."
Kirito: "Can you tell me how many substrings of s can be arranged as a palindrome?"
You: "Sure, it is not hard."
Kirito: "Can you tell me how many substrings of a substring of s can be arranged as a palindrome?"
The first line of the input data contains an integer T (1 ≤ T ≤ 250) specifying
the number of test cases.
Each test case starts with a line contains two integers n;m (1 ≤ n,m ≤ 50000), denoting the length of s and the number of queries. Then one line contains a string s which consists of only lowercase letters. Each of the following m lines contains two integers li, ri (1 ≤ li ≤ ri ≤ n), denoting a query substring s[li,...,ri] of s. No more than 5 test cases have max(n;m) > 1000.
For each query, please output the number of substrings of s[li,...,ri] that can be arranged as a palindrome.