B'A string t is said to be k -good if there exists at least one substring ^ dagger of length k which is not a palindrome ^ ddagger . Let f(t) denote the sum of all values of k such that the string t is k -good. You are given a string s of length n . You will have to answer q of the following queries: ^ dagger A substring of a string z is a contiguous segment of characters from z . For example, " mathtt{defor} ", " mathtt{code} " and " mathtt{o} " are all substrings of " mathtt{codeforces} " while " mathtt{codes} " and " mathtt{aaa} " are not. ^ ddagger A palindrome is a string that reads the same backwards as forwards. For example, the strings " texttt{z} ", " texttt{aa} " and " texttt{tacocat} " are palindromes while " texttt{codeforces} " and " texttt{ab} " are not. Each test contains multiple test cases. The first line contains a single integer t ( 1 <= q t <= q 2 cdot 10^4 ) -- the number of test cases. The description of the test cases follows. The first line of each test case contains two integers n and q ( 2 <= n <= 2 cdot 10^5, 1 <= q <= 2 cdot 10^5 ), the size of the string and the number of queries respectively. The second line of each test case contains the string s . It is guaranteed the string s only contains lowercase English characters. The next q lines each contain two integers, l and r ( 1 <= l < r <= n ). It is guaranteed the sum of n and the sum of q both do not exceed 2 cdot 10^5 . For each query, output f(s_ls_{l + 1} ldots s_r) . In the first query of the first test case, the string is mathtt{aaab} . mathtt{aaab} , mathtt{aab} and mathtt{ab} are all substrings that are not palindromes, and they have lengths 4 , 3 and 2 respectively. Thus, the string is 2 -'...