题目描述

这是一个美好的下午，小W和小C在竹林里切磋捆竹竿的技艺。

竹林里有无数根完全一样的短竹子，每一根竹子由 \(n\) 节组成。

这些竹子比较特别，
每一节都被染上了颜色。
可能的颜色一共26种，
分别用小写英文字母 \(a\) 到 \(z\) 表示。
也就是说，
如果把竹子的底端到顶端的颜色按顺序写出来，
可以排成一个由小写英文字母组成的字符串。

小W和小C都是捆竹竿的高手，
他们知道怎样才能把零散的短竹子捆成一整根长竹竿。
初始时你拿着一根短竹子作为当前的竹竿。
每次你可以选择一根短竹子，
短竹子底端若干节（可以是 0 节）与竹竿的最上面若干节对应地一节一节捆起来，
而短竹子前面剩下的节伸出去，
这样就得到了一根更长的竹竿。
注意，竹子的底端是靠近根部的那一端，不可以颠倒。

小W对竹竿的审美要求很高，他捆竹竿时有一个癖好：
如果两根竹子的某两节被捆在了一起，那么它们的颜色必须相同。

我们假设一根短竹子从底端到顶端每节的颜色为 aba。

那么两根竹子可以首尾捆在一起，可以得到一根颜色为 abaaba 的竹竿；
也可以将第一根顶端的一节 a 与第二根底端的一节 a 捆在一起，得到一根颜色为 ababa 的竹竿；
还可以直接将每一节都对应起来，捆成一根颜色为 aba 的竹竿。

假设我们在颜色为 ababa 的竹竿顶端再捆一根竹子，
则可以捆成 ababaaba，abababa 和 ababa 三种不同的情况。

但是小C在这个问题上有不同的看法，
他认为小W捆不出很多种长度不同的竹竿。
小W非常不服，
于是他找到了你——现在请你求出在竹竿长度不超过 \(w\) 的情况下，
小W可以捆出多少种长度不同的竹竿。
其中，竹竿的长度指从底端到顶端的竹子的节的个数。

注意：如果 \(w<n\)，则没有合法的长度，此时答案为 0。

输入

第一行，包含1个整数 \(T\)，为数据组数。

每组数据的第一行，
包含2个正整数 \(n\) 和 \(m\)，表示短竹子的长度和竹竿的长度上限。

每组数据的第二行，包含一个长度为 \(n\) 的字符串，
该字符串仅由小写英文字母构成，
表示短竹子从底端到顶端每节的颜色。

输出

共 \(T\) 行，每行包含一个整数表示捆成竹竿的不同长度种数。

样例一

输入

1
4 11
bbab

输出

5

解释

可以捆成长度不超过 \(11\) 的竹竿有 \(6\) 种不同的情况:

bbab
bbabbab
bbabbbab
bbabbabbab
bbabbabbbab
bbabbbabbab


后两种竹竿长度相同,因此不同长度的竹竿共有 \(5\) 种。长度分别为：\(4, 7, 8, 10, 11\)。

样例二

输入

2
44 1000
baaaaaabaabbaaabbbbabbbaaabbbababaaabaaabaaa
41 1000
abaabbabaaabaabbbbbbbbbbbababbbbaaabaabbb

输出

195
24

样例三

见样例数据下载。

数据范围限制

来源

WC2016