Migrated from Lutece 3275 Before I Rise

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Tags: KMP，Periodicity Lemma，同余最短路

本题面由 空気力学の詩 友情提供

---

Death is not the end of life, but the completion of life.

月歌在一次讨伐『星癌体』的过程中发现了许多刻有神秘符号的能量石，初步估计发现的能量石约有 $10^{10^{10^{10}}}$ 个。

初始时每个能量石上都刻有完全相同的，长为 $n$ 的字符串 $S=S[1,n]$，根据调查可以确定 $S$ 仅由小写英文字母构成，并且一块能量石所含的能量恰为该能量石上刻有的字符串长度。

能量石可以通过融合操作得到能量更大，即刻有的字符串长度更长的能量石，具体的融合规则如下：

• 初始时月歌选取任意一块能量石作为融合的基石；
• 每次月歌可以选择一块未经过操作的初始能量石，把它和先前融合得到的基石进行融合，得到一块新的基石；

而同样的两块能量石有多种融合方式，月歌可以自行选择其中的一种合法方式进行融合。

具体地，如果要将刻有长为 $m$ 的字符串 $T$ 的基石和刻有长为 $n$ 的字符串 $S$ 的初始能量石进行融合，一种合法的方案形如：

• 选择一个 $l\in[0,n]$，需要满足 $\forall i\in[1,l], T[m-l+i]=S[i]$，注意当 $l=0$ 时本条限制视为默认满足；
• 融合后得到的字符串 $T'$ 长为 $m+n-l$，由 $T$ 拼接上 $S$ 的长为 $n-l$ 的后缀得到，即 $T'=T+S[l+1,n]$；

例如当初始能量石上刻有 $S=\texttt{aba}$ 时，初始时选定基石 $T=\texttt{aba}$，则第一次融合可以得到三种可能的 $T'$：

• 选定 $l=0$，得到 $T'=\texttt{abaaba}$；

• 选定 $l=1$，得到 $T'=\texttt{ababa}$；

• 选定 $l=3$，得到 $T'=\texttt{aba}$；

• 注意当 $l=2$ 时不满足限制，因此无法进行融合；

假设月歌选定新的基石为 $T=\texttt{ababa}$，则第二次融合又可以得到三种可能的 $T'$：

• 选定 $l=0$，得到 $T'=\texttt{ababaaba}$；
• 选定 $l=1$，得到 $T'=\texttt{abababa}$；
• 选定 $l=3$，得到 $T'=\texttt{ababa}$；
• 注意当 $l=2$ 时不满足限制，因此无法进行融合；

现在面对着如此多数量的能量石，月歌想要知道，在能量石的能量不超过 $w$ 的情况下，可以得到多少种不同能量的能量石。

注意：当 $w<n$ 时，认为没有合法的能量石，此时答案为 $0$。

Input

输入的第一行包括一个正整数 $t$ ，代表测试数据的数量。

每组数据的第一行包含两个个正整数 $n,w$，表示初始能量石上刻有的字符串的长度和能量石的能量上限。

每组数据的第二行包含一个长度为 $n$ 的字符串 $S$，该字符串仅由小写英文字母构成，表示表示初始能量石上刻有的字符串。

Output

每组数据输出一行一个数表示可以得到的能量石的不同能量种数。

Samples

1
3 8
aba

5

1
4 11
bbab

5

5
22 1132
abbabbababbababbabbaba
22 938
bbabbababbababbabbabab
22 1013
abbababbababbabbababba
22 1066
abbabbababbababbabbaba
22 958
ababbabbababbababbabba

1061
867
957
995
887

Constraints

$1\le t\le 5,1\le n\le 5\times 10^5,1\le w\le 10^{18}$

对于所有的测试数据，保证所有的字符串均由小写字母构成。

Note

对于样例二，可以得到的且能量不超过 $11$ 的能量石共有以下 $6$ 种：

$\texttt{bbab},\texttt{bbabbab},\texttt{bbabbab},\texttt{bbabbabbab},\texttt{bbabbabbbab},\texttt{bbabbbabbab}$，其中后两种能量石的能量相同，因此不同能量的能量石共有 $5$ 种，能量分别为 $4,7,8,10,11$。

Resources

2024 UESTC ICPC Training for String