問題文

$T$ 個のテストケースが与えられるので、それぞれについて以下の問題を解いてください。

長さが $N$ の文字列 $S$ が与えられます。

あなたは空文字列 $U$ を持っており、以下の操作を何度でも行うことができます。

• $U$ に $S$ を連結する。つまり、$U$ を $U S$ へ置き換える。

文字列 $U$ の連続する部分文字列に長さが $M$ 以上の回文が含まれるために必要な操作回数の最小値を求めてください。

なお、何回操作を行っても達成することが不可能な場合には -1 を出力してください。

制約

• $1 \leq T \leq 2 \times 10^{5}$
• $1 \leq N \leq 2 \times 10^{5}$
• $1 \leq M \leq 10^{9}$
• $S$ は英小文字からなる長さが $N$ の文字列
• $1$ つの入力に含まれるテストケースについて、$N$ の総和は $2 \times 10^{5}$ 以下である。
• $T, N, M$ は整数である。

入力

入力は以下の形式で標準入力から与えられる。

$T$
$\text{case}_1$
$\vdots$

$\text{case}_T$

各テストケースは以下の形式で与えられる。

$N$ $M$ 
$S$ 

出力

$T$ 行出力せよ。$i$ 行目には $i$ 番目のテストケースについての問題の答えを出力せよ。

サンプル

3
4 10
acbc
3 2357
aba
4 2
sepa

3
786
-1