给你一个长度为 $N$ 的字符串 $S$。

你有一个空字符串 $U$，你可以进行下述操作任意多次。

• 把 $S$ 接到 $U$ 的末尾。也就是说，把 $U$ 变成 $US$。

要使 $U$ 含有一个长度至少是 $M$ 的回文子串，至少要操作多少次？

如果不可能达成目标，输出 -1。

一个输入文件里有 $T$ 组数组。

限制

• $1 \le T \le 2\times 10^5$
• $1 \le N \le 2\times 10^5$
• $1 \le M \le 10^9$
• $S$ 由小写英文字母构成。
• 一个输入文件里 $N$ 的总和不超过 $2\times 10^5$。
• $T$，$N$，$M$ 是整数。

本题有 50 个测试点，其中有 19 个测试点满足 $T$ 组测试的 $M$ 之和小于 $2\times 10^6$。

输入

从文件 palindrome.in 中读入数据。

第一行包含一个整数 $T$。接下来有 $2T$ 行，每两行表示一组测试。每组测试的第一行包含两个整数 $N, M$，第二行包含一个字符串 $S$。

输出

输出到文件 palindrome.out 中。

输出 $T$ 行。第 $i$ 行应包含一个整数，表示第 $i$ 组测试的答案。

样例输入 1

3
4 10
acbc
3 2357
aba
4 2
sepa

样例输出 1

3
786
-1

对于第一组测试，3 次操作过后，$U =$ acbcacbcacbc，$U$ 的子串 cbcacbcacbc 是一个长度是 $11$ 的回文串。

附件样例