You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

克露丝卡尔酱今天也被奇怪的字符串难题困扰着！

身旁的后辈歪着头：“前辈不是最擅长这种问题吗？”

克露丝卡尔酱的脸微微发红：“哼、哼！当然难不倒我啦！”

题目描述

字符串的 游程（run） 定义为仅包含一种字符且不可扩展的非空子串，例如 aabaa 共有三个游程，分别为 aa、b、aa。

给定长度为 $n$ 的字符串，你可以将其切成三个非空字符串并以任意顺序重新拼接为一个字符串，计算有多少种不同的方案可以使得新字符串的游程数量为 $k$。

注意：两个方案不同当且仅当切分位置不同或拼接顺序不同，拼接顺序共有 $6$ 种。

输入格式

本题有多组测试数据。

首先输入一行，包含一个整数 $T$ ($1\le T\le 10^5$)，表示测试数据组数。

每组数据首先输入一行，包含两个整数，分别表示字符串长度 $n$ ($3\le n\le 10^5$) 和游程数量 $k$ ($1\le k\le n$)。

之后输入一行，包含一个长度为 $n$ 的字符串，字符串仅包含小写英文字母。

保证 $\sum n\le 10^5$。

输出格式

输出 $T$ 行，每行一个整数，表示方案数。

样例 #1

样例输入 #1

2
8 5
abbccaba
3 1
abc

样例输出 #1

45
0

提示

在第一组样例中，将字符串切成 abb、cc、aba 三段，把第三段放到最前面，得到 abaabbcc，游程数量为 $5$，满足要求。