write a go solution for Description:
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:

- Given l and r (l<r), find the value of f(s_ls_l+1ldotss_r).

^dagger A substring of a string z is a contiguous segment of characters from z. For example, "mathttdefor", "mathttcode" and "mathtto" are all substrings of "mathttcodeforces" while "mathttcodes" and "mathttaaa" are not.

^ddagger A palindrome is a string that reads the same backwards as forwards. For example, the strings "textttz", "textttaa" and "texttttacocat" are palindromes while "textttcodeforces" and "textttab" are not.

Input Format:
Each test contains multiple test cases. The first line contains a single integer t (1<=t<=2*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*10^5,1<=q<=2*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*10^5.

Output Format:
For each query, output f(s_ls_l+1ldotss_r).

Note:
In the first query of the first test case, the string is mathttaaab. mathttaaab, mathttaab and mathttab are all substrings that are not palindromes, and they have lengths 4, 3 and 2 respectively. Thus, the string is 2-good, 3-good and 4-good. Hence, f(mathttaaab)=2+3+4=9.

In the second query of the first test case, the string is mathttaaa. There are no non-palindromic substrings. Hence, f(mathttaaa)=0.

In the first query of the second test case, the string is mathttabc. mathttab, mathttbc and mathttabc are all substrings that are not palindromes, and they have lengths 2, 2 and 3 respectively. Thus, the string is 2-good and 3-good. Hence, f(mathttabc)=2+3=5. Note that even though there are 2 non-palindromic substrings of length 2, we count it only once.. Output only the code with no comments, explanation, or additional text.