Puppy and Palindromes

All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
A recent survey suggested that almost everybody knows that a palindrome is a string which reads the same backwards as forwards. More recently, puppy Tuzik invented a brandnew concept: Kpalindromes. A string is called a Kpalindrome if it is possible to make it a usual palindrome by replacing at most K characters. For example, a string abb can be made a palindrome by replacing one character, the second b with an a. Please note, that according to the definition, a usual palindrome is a Kpalindrome for any nonnegative integer K.
Today, Tuzik was walking in a garden and came across a string S of N characters. Now, he wants to know the sum of the lengths of all substrings of S which are Kpalindromes. Note that two substrings are considered to be different if they cover the different ranges of indices, even if they are equal as strings.
Input
The first line of input contains an integer T denoting the number of test cases. Each of the next T lines contains a description of a separate test case.
The only line of the test case description contains two integers N and K followed by string S, all separated by single spaces. S consists of lowercase Latin characters only.
Output
For each test case, output a single line containing one integer: the answer for the test case.
Constraints
 1 ≤ T ≤ 5
 1 ≤ N ≤ 10^{5}
 0 ≤ K ≤ 5
Example
Input: 2 7 0 abacaba 7 1 abacaba Output: 28 56
Explanation
Test case 1:
There are:
 7 0palindromes with length 1 (just each character)
 3 0palindromes with length 3 (aba, aca, aba)
 1 0palindrome with length 5 (bacab)
 1 0palindrome with length 7 (abacaba) .
Test case 2:
There are:
 7 1palindromes with length 1 (just each character)
 6 1palindromes with length 2 (each substring with length 2)
 5 1palindromes with length 3 (each substring with length 3)
 3 1palindromes with length 5 (abaca,bacab, acaba)
 1 1palindrome with length 7 (abacaba) .
Author:  pavel1996 
Tester:  kostya_by 
Editorial  http://discuss.codechef.com/problems/PUPPYPLM 
Tags  constructive, cook67, hashing, palindromes, pavel1996 
Date Added:  23062015 
Time Limit:  7 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 