#include <bits/stdc++.h>
#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define REP(I, N) for (int I = 0; I < (N); ++I)
#define REPP(I, A, B) for (int I = (A); I < (B); ++I)
#define RI(X) scanf("%d", &(X))
#define RII(X, Y) scanf("%d%d", &(X), &(Y))
#define RIII(X, Y, Z) scanf("%d%d%d", &(X), &(Y), &(Z))
#define DRI(X) int (X); scanf("%d", &X)
#define DRII(X, Y) int X, Y; scanf("%d%d", &X, &Y)
#define DRIII(X, Y, Z) int X, Y, Z; scanf("%d%d%d", &X, &Y, &Z)
#define RS(X) scanf("%s", (X))
#define CASET int ___T, case_n = 1; scanf("%d ", &___T); while (___T-- > 0)
#define MP make_pair
#define PB push_back
#define MS0(X) memset((X), 0, sizeof((X)))
#define MS1(X) memset((X), -1, sizeof((X)))
#define LEN(X) strlen(X)
#define PII pair<int,int>
#define VI vector<int>
#define VPII vector<pair<int,int> >
#define PLL pair<long long,long long>
#define VPLL vector<pair<long long,long long> >
#define F first
#define S second
typedef long long LL;
using namespace std;
const int MOD = 1e9+7;
const int SIZE = 3005;
int dp[SIZE][SIZE];
int dp2[SIZE][SIZE];
char s[SIZE];
int main(){
    CASET{
        DRII(n,K);
        RS(s+1);
        if(K>2)puts("0");
        else if(K==0){
            printf("%d\n",n*26+26);
        }
        else{
            MS0(dp);
            MS0(dp2);
            REPP(i,1,n+1)dp2[i][i]=1;
            REPP(j,1,n){
                for(int k=1;k+j<=n;k++){
                    int ll=k,rr=k+j;
                    if(s[ll]==s[rr])dp2[ll][rr]=max(dp2[ll][rr],dp2[ll+1][rr-1]+2);
                    dp2[ll][rr]=max(dp2[ll][rr],dp2[ll+1][rr]);
                    dp2[ll][rr]=max(dp2[ll][rr],dp2[ll][rr-1]);
                }
            }
            int ma=0;
            for(int i=1;i<n;i++){
                for(int j=n;j>i;j--){
                    if(s[i]==s[j])dp[i][j]=dp[i-1][j+1]+2;
                    else dp[i][j]=max(dp[i-1][j],dp[i][j+1]);
                    ma=max(ma,dp[i][j]);
                }
            }
            REPP(i,1,n+1)ma=max(ma,dp[i-1][i+1]+1);
            int an=0;
            REP(i,n+1){
                int me=0;
                me=dp[i][i+1]+1;
                if(me>=ma+K){
                    an+=26;
                    continue;
                }
                bool used[26]={};
                REPP(j,1,n+1){
                    if(j<=i){
                        if(dp2[j+1][i]+dp[j-1][i+1]+2>=ma+K)used[s[j]-'a']=1;
                    }
                    else{
                        if(dp2[i+1][j-1]+dp[i][j+1]+2>=ma+K)used[s[j]-'a']=1;
                    }
                }
                REP(j,26)
                    if(used[j]){
                        an++;
                    }
            }
            printf("%d\n",an);
        }
    }
    return 0;
}

import java.util.Scanner;

/**
 *
 * @author abhishek
 */
public class LongestPalSeq {
    
    
    //lsc[i][j] = length of longest common subsequence between S[0,i] and rev(S)[0,j] i.e. S[n-1-j]
    private static int[][] lcs(char[] arr,char[] b){
        int[][] lcs = new int[arr.length+1][b.length+1];
        int i,j;
        for(i=1;i<=arr.length;i++){
            for(j=1;j<=b.length;j++){
                    if(arr[i-1] == b[j-1]){
                        lcs[i][j] = 1+lcs[i-1][j-1];
                    }
                    else{
                        lcs[i][j] = Math.max(lcs[i][j-1], lcs[i-1][j]);
                    }
                }
        }
        return lcs;
    }
    
    
    
    
    
    //lps[i][j] = maximumlength of any palindrome in S[i][j]
    private static int[][] calcLPS(char[] arr){
        int[][] lps = new int[arr.length][arr.length];
        int i,j,k;
        for(i=0;i<arr.length;i++){
            lps[i][i] = 1;
        }
        //k denotes the length of substring
        //all 1 length are have already been covered
        for(k=2;k<=arr.length;k++){
            for(i=0;i<=arr.length-k;i++){
                j = i+k-1;
                if(j==i+1){
                    //i.e. only two characters
                    if(arr[i]==arr[j]){
                        lps[i][j] = 2;
                    }
                    else{
                        lps[i][j] = 1;
                    }
                }
                else{
                if(arr[i] == arr[j]){
                    lps[i][j] = 2+lps[i+1][j-1];
                }
                else{
                    lps[i][j] = Math.max(lps[i+1][j],lps[i][j-1]);
                }
                }
            }
        }
        
        
        return lps;
    }
    

    
    
    
    private static int calcWays(int[][] lps,int[][] lcs,char[] arr,int lp){
        int n = arr.length;
        int i,j,k;
        int ans = 0;
        //there are n+1 positions to insert a new character
        //also length of palindrome cannot be increased more than 2
        //we will try to put character at each of these positions and try to 
        //get the length of palindrome, if it increases then we add this to final answer
        int[] table = new int[26];
        //i denotes the position of new character will be added
        //just assuming strings from index 1 for lcs
        for(i=0;i<=arr.length;i++){
            //consider i as a center, then new pal will always be of odd length
            int x = Math.max(lps[0][n-1], 1+lcs[i][n-i]*2);
            for(k=0;k<=25;k++){
                table[k] = x;
            }
            
            //consider the case when i is not the center
            for(j=0;j<arr.length;j++){
                if(j<i){
                    x = lcs[j][n-i]*2+(j+1<n?lps[j+1][i-1]:0);
                }
                else if(j>i){
                    x = lcs[i][n-j-1]*2 + lps[i][j-1];
                }
                else{
                    x = lcs[i][n-j-1]*2;
                }
                table[arr[j]-'a'] = Math.max(table[arr[j]-'a'], (x+2));
            }
            for(j=0;j<=25;j++){
                if(table[j] >= lps[0][n-1]+lp){
                    ans++;
                }
            }
        }
        
        
        
        
        
        
        
        return ans;
    }
    
    public static void main(String[] args){
        
        
        
        Scanner scan = new Scanner(System.in);
        int i,t,k,n;
        t = scan.nextInt();
        for(i=0;i<t;i++){
        
            n = scan.nextInt();
            k = scan.nextInt();
            
            char[] arr = scan.next().toCharArray();
            if(k == 0){
                System.out.println((26*(n+1)));
            }
            else if(n == 1){
                System.out.println(2);
            }
            else{
                int[][] lps = calcLPS(arr);
                int[][] lcs = lcs(arr,reverse(arr));
                int ans = calcWays(lps,lcs,arr,k);
                System.out.println(ans);
            }
        
        
        
        /*for(int i=0;i<lcs.length;i++){
            for(int j=0;j<lcs.length;j++){
                System.out.print(lcs[i][j] + " ");
            }
            System.out.println();
        }*/
        }
    }
    private static char[] reverse(char[] arr){
        char[] rev = new char[arr.length];
        int i,n= arr.length-1;
        for(i=0;i<=n;i++){
            rev[i] = arr[n-i];
        }
        return rev;
    }
}

 

#!/bin/python3

import math
import os
import random
import re
import sys

# Complete the longestPalindromicSubsequence function below.
def max(x, y):
    if(x > y):
        return x
    return y

    
def stripwordfromsameletters(str):
    if len(str) > 1:
        el1 = ""
        i = 0
        for el in str:
            found = False
            for rel in str[i + 1:]:
                if el == rel:
                    found = True
                    break
            i += 1
            if not found:
                el1 += el
        return el1
    return str
    
    
def append_if_not_find(arr, e):
    for a in arr:
        if e == a:
            return arr
    arr += e
    return arr    

    
def content_combinations(ltr_pos_ar, st, beg, end, k):
    cont = st[beg+1:end]
    length = len(cont)
    if length < 2 and k == 2:
        return True
    if length == 0 and k == 1:
        for i in range(97, 123):
            ltr_pos_ar[beg + 1] = append_if_not_find(ltr_pos_ar[beg + 1], chr(i))
        return True
    if length > 0 and k == 1:
        for i in range(length):
            for j in range(length + 1):
                ltr_pos_ar[beg + j + 1] = append_if_not_find(ltr_pos_ar[beg + j + 1], cont[i])
        return True

    for i in range(length):
        for j in range(length):
            if j > i:
                ltr_pos_ar[beg + j + 2] = append_if_not_find(ltr_pos_ar[beg + j + 2], cont[i])
            elif i > j:
                ltr_pos_ar[beg + j + 1] = append_if_not_find(ltr_pos_ar[beg + j + 1], cont[i])
    return True


def edge_combinations(ltr_pos_ar, st, left_beg, left_end, right_beg, right_end, k):
    edgeleft = st[left_beg:left_end]
    edgeright = st[right_beg:right_end]
    stredgeleft = stripwordfromsameletters(edgeleft)
    if k == 1 and right_beg - left_end == 2:
        content_combinations(ltr_pos_ar, st, left_beg - 1, left_end, 2)
        stredgeleft += st[left_end + 1]
    for ll in stredgeleft:
        ltr_pos_ar[right_beg] = append_if_not_find(ltr_pos_ar[right_beg], ll)
        for i in range(len(edgeright)):
            ltr_pos_ar[right_beg + i + 1] = append_if_not_find(ltr_pos_ar[right_beg + i + 1], ll)
    stredgeright = stripwordfromsameletters(edgeright)
    if k == 1 and right_beg - left_end == 2:
        content_combinations(ltr_pos_ar, st, right_beg - 1, right_end, 2)
        stredgeright += st[right_beg - 2]
    for rl in stredgeright:
        ltr_pos_ar[left_end] = append_if_not_find(ltr_pos_ar[left_end], rl)
        for i in range(len(edgeleft)):
            ltr_pos_ar[left_end - i - 1] = append_if_not_find(ltr_pos_ar[left_end - i - 1], rl)
    return True


def lps(ae, st, n, k):
    # Create a table to store results of sub problems
    L = [[0 for x in range(n)] for x in range(n)]

    # Strings of length 1 are palindrome of length 1
    for i in range(n):
        L[i][i] = 1

    for cl in range(2, n + 1):
        # cl = current subsequence length
        for i in range(n - cl + 1):
            # j = last character
            j = i + cl - 1
            if st[i] == st[j]:
                # if first and last characters of the substring are the same
                if cl == 2:
                    L[i][j] = 2
                else:
                    L[i][j] = L[i + 1][j - 1] + 2
                # pl = current longest palindromic sequence
                pl = L[i][j]

                if pl - len(ae) >= 2:
                    # if current longest palindromic is greater plus 2 than the ea list then it fills it with
                    # default
                    for ln in range(len(ae), pl - 1):
                        ae.append({"pl": ln + 2, "ea": []})

                kid = []
                if pl > 3:
                    for ie in range(len(ae[pl - 4]['ea'])):
                        e = ae[pl - 4]['ea'][ie]
                        if e['beg'] > i and e['end'] < j:
                            kid.append({"idx": ie, "pl": pl - 4, "k": k})

                if k == 1:
                    if pl > 4:
                        for ie in range(len(ae[pl - 5]['ea'])):
                            e = ae[pl - 5]['ea'][ie]
                            if e['beg'] > i and e['end'] < j:
                                kid.append({"idx": ie, "pl": pl - 5, "k": 2})

                ae[pl - 2]['ea'].append({"beg": i, "end": j, "kid": kid, "prn": {}, "nxt": {}, "pl": pl-2})
            else:
                L[i][j] = max(L[i][j - 1], L[i + 1][j])

    return L[0][n - 1]


def getways(ltr_pos_ar, ae, st, n, k):

    scount = 0

    if len(ae) == 0:
        # if the string contains no double letters
        content_combinations(ltr_pos_ar, st, -1, n, k)
        for x in ltr_pos_ar:
            scount += len(x)
        return scount

    # get the element from the ae array with the longest palindromic number
    prn_pl = len(ae) + 1
    pl = len(ae) - 1
    ple = ae[pl]
    ge = ple['ea']
    len_ge = len(ge)
    e, pl = ge[0], ple['pl'] - 2
    e['kid_idx'], e['k'] = 0, k
    ck = k
    root_kid = [{"idx": 0, "pl": pl, "k": ck}]
    if len_ge > 1:
        # if it has siblings
        for ie in range(len(ge[:len_ge - 1])):
            coord = {"idx": ie + 1, "pl": pl, "k": k}
            ge[ie]['nxt'] = coord
            ge[ie + 1]['kid_idx'] = ie + 1
            root_kid.append(coord)

    if k == 1 and len(ae) > 1:
        # if k =1 and ae is over 1
        el = len(ae) - 2
        ple = ae[el]
        ge = ple['ea']
        len_ge = len(ge)
        if len_ge > 0:
            len_kid = len(root_kid)
            last_kid_e = root_kid[len_kid - 1]
            last_kid_pl = last_kid_e['pl']
            last_kid_idx = last_kid_e['idx']
            last_kid = ae[last_kid_pl]['ea'][last_kid_idx]
            coord = {"idx": 0, "pl": el, "k": 2}
            last_kid['nxt'] = coord
            ge[0]['kid_idx'] = len_kid
            root_kid.append(coord)
            for ie in range(len(ge[:len_ge - 1])):
                coord = {"idx": ie + 1, "pl": pl - 1, "k": 2}
                ge[ie]['nxt'] = coord
                ge[ie + 1]['kid_idx'] = ie + len_kid + 1
                root_kid.append(coord)

    # left, right = st[:e['beg']], st[e['end'] + 1:]
    nxt, kid = e['nxt'], e['kid']
    prn, idx = {}, 0
    if pl <= 1:
        # if longest palindromic is 3 compute the inner substring inside the string: x..in..x
        e['cc'] = content_combinations(ltr_pos_ar, st, e['beg'], e['end'], ck)
    # Compute the outer, left and right substrings of the string: left..x..in..x..right
    edge_combinations(ltr_pos_ar, st, 0, e['beg'], e['end'] + 1, len(st), ck)

    # print(f" FIRST LEVEL:{pl} k:{k} {e}")
    # print(ltr_pos_ar)
    proceed = True
    prn_beg = -1
    prn_end = len(st)
    prn_kid = root_kid

    while proceed:
        if len(kid) > 0:
            # if it has children go to first child
            prn_kid = kid

            # prn_idx = e['kid_idx']
            ck = e['k']
            prn_pl = e['pl']
            prn_beg, prn_end = e['beg'], e['end']

            pl = kid[0]['pl']
            ple = ae[pl]
            ge = ple['ea']
            e = ge[kid[0]['idx']]
            e['kid_idx'], e['prn'] = 0, {'pl': prn_pl, 'idx': idx}
            idx = kid[0]['idx']

            if len(prn_kid) > 1:
                # if it is in turn not the last kid create a reference to its sibling
                coord_next = prn_kid[1]
                e['nxt'] = coord_next
                ae[coord_next['pl']]['ea'][coord_next['idx']]['kid_idx'] = 1
            else:
                e['nxt'] = {}

            # left = st[prnbeg + 1:e['beg']]
            # right = st[e['end'] + 1:prnend]
            if prn_pl - pl == 3:
                if k == 1 and ck == 2:
                    # if parent k = 2 and app k = 1 and difference = 3 then halt the loop
                    e['kid'] = []
                    prn = e['prn']
                    nxt = e['nxt']
                    kid = e['kid']
                    continue
                ck = 2

            e['k'] = ck

            if pl <= 1 and 'cc' not in e:
                # if longest palindromic is 3 compute the inner substring inside the string: x..in..x

                e['cc'] = content_combinations(ltr_pos_ar, st, e['beg'], e['end'], e['k'])
            # Compute the outer, left and right substrings of the string: left..x..in..x..right
            edge_combinations(ltr_pos_ar, st, prn_beg + 1, e['beg'], e['end'] + 1, prn_end, e['k'])

            # print(f" CHILD LEVEL:{pl} k:{ck} {e}")
            # print(ltr_pos_ar)
        elif nxt != {}:
            # if it has siblings go to next sibling
            pl = nxt['pl']
            ple = ae[pl]
            ge = ple['ea']
            e = ge[nxt['idx']]
            e['prn'] = prn
            idx = nxt['idx']

            if len(prn_kid) > e['kid_idx'] + 1:
                # if it is in turn not the last kid then create a reference to its sibling
                coord_next = prn_kid[e['kid_idx'] + 1]
                e['nxt'] = coord_next
                ae[coord_next['pl']]['ea'][coord_next['idx']]['kid_idx'] = e['kid_idx'] + 1
            else:
                e['nxt'] = {}

            # left = st[prnbeg + 1:e['beg']]
            # right = st[e['end'] + 1:prnend]
            if prn_pl - pl == 3:
                if k == 1 and ck == 2:
                    # if parent k = 2 and app k = 1 and difference = 3 then halt the loop
                    e['kid'] = []
                    prn = e['prn']
                    nxt = e['nxt']
                    kid = e['kid']
                    continue
                ck = 2
            e['k'] = ck
            if pl <= 1 and 'cc' not in e:
                # if longest palindromic is 3 compute the inner substring inside the string: x..in..x
                e['cc'] = content_combinations(ltr_pos_ar, st, e['beg'], e['end'], e['k'])
            # Compute the outer, left and right substrings of the string: left..x..in..x..right
            edge_combinations(ltr_pos_ar, st, prn_beg + 1, e['beg'], e['end'] + 1, prn_end, e['k'])
            # print(f" NEXT LEVEL:{pl} k:{e['k']} {e}")
            # print(ltr_pos_ar)
        elif prn != {}:
            pl = prn['pl']
            ple = ae[pl]
            kid_idx = e['kid_idx']

            e = ple['ea'][prn['idx']]

            if kid_idx == len(e['kid']) - 1:
                # if is the last kid
                e['kid'] = []

            if e['prn'] != {}:

                prn_pl = e['prn']['pl']
                ple = ae[prn_pl]
                ep = ple['ea'][e['prn']['idx']]
                prn_beg = ep['beg']
                prn_end = ep['end']
                prn_kid = ep['kid']
                ck = ep['k']
            else:
                prn_beg = -1
                prn_end = len(st)
                prn_kid = root_kid
                prn_pl = len(ae) + 1
                ck = k

            # print(f" PARENT BACK LEVEL:{pl} k:{e['k']} {e}")
        prn = e['prn']
        nxt = e['nxt']
        kid = e['kid']
        proceed = not (nxt == {} and len(kid) == 0 and prn == {})

    # print(ltr_pos_ar)
    # Iterate the array
    for x in ltr_pos_ar:
        scount += len(x)
    # print(f"scount: {scount}")
    return scount

    
def longestPalindromicSubsequence(st, k):
    global n
    ways = 0
    if k == 0:
        return 26 * (n + 1)
    if k >= 3:
        return 0
    
    ae = []
    slong = lps(ae, st, n, k)
    # print(f"longest current palindromic for string {s} is: {slong}")
    ltr_pos_ar = ['' for i in range(n + 1)]
    ways = getways(ltr_pos_ar, ae, st, n, k)
    return ways

    
if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    q = int(input())

    for q_itr in range(q):
        nk = input().split()

        n = int(nk[0])

        k = int(nk[1])

        s = input()

        result = longestPalindromicSubsequence(s, k)

        fptr.write(str(result) + '\n')

    fptr.close()

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int max(int x,int y);
int solve1(int x,int y);
int solve2(int x,int y);
char str[3001];
int dp1[3000][3000],dp2[3000][3000],b[26][3001],n;

int main(){
  int q,ans,i,j,k,l;
  scanf("%d",&q);
  while(q--){
    memset(dp1,-1,sizeof(dp1));
    memset(dp2,-1,sizeof(dp2));
    for(i=ans=0;i<26;i++)
      b[i][0]=0;
    scanf("%d%d%s",&n,&k,str);
    for(i=0;i<n;i++)
      b[str[i]-'a'][++b[str[i]-'a'][0]]=i;
    for(i=0;i<=n;i++)
      for(j=0;j<26;j++)
        if(solve2(i-1,i)+1>=solve1(0,n-1)+k || !k)
          ans++;
        else
          for(l=1;l<=b[j][0];l++)
            if((b[j][l]<i && solve1(b[j][l]+1,i-1)+solve2(b[j][l]-1,i)+2>=solve1(0,n-1)+k) || (b[j][l]>=i && solve1(i,b[j][l]-1)+solve2(i-1,b[j][l]+1)+2>=solve1(0,n-1)+k)){
              ans++;
              break;
            }
    printf("%d\n",ans);
  }
  return 0;
}
int max(int x,int y){
  return (x>y)?x:y;
}
int solve1(int x,int y){
  if(x>y)
    return 0;
  if(x==y)
    return 1;
  if(dp1[x][y]!=-1)
    return dp1[x][y];
  if(str[x]==str[y])
    dp1[x][y]=solve1(x+1,y-1)+2;
  else
    dp1[x][y]=max(solve1(x+1,y),solve1(x,y-1));
  return dp1[x][y];
}
int solve2(int x,int y){
  if(x>=y || x<0 || y>=n)
    return 0;
  if(dp2[x][y]!=-1)
    return dp2[x][y];
  if(str[x]==str[y])
    dp2[x][y]=solve2(x-1,y+1)+2;
  else
    dp2[x][y]=max(solve2(x-1,y),solve2(x,y+1));
  return dp2[x][y];
}