题目描述

英小文字からなる長さ $N$ の文字列 $S$ と正整数 $K$ が与えられます。

以下の条件を満たす長さ $K$ の文字列 $S'$ が存在するか判定してください。

• $S,\ S'$ をこの順に結合して得られる文字列は回文である
• $S',\ S$ をこの順に結合して得られる文字列は回文である

$T$ 個のテストケースが与えられるのでそれぞれについて判定してください。

输入格式

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

$T$ $\mathrm{case}_1$ $\vdots$ $\mathrm{case}_T$

各ケースは以下の形式で与えられます。

$N$ $K$ $S$

输出格式

$T$ 行出力せよ。$i$ 行目には $i$ 番目のテストケースについて、条件を満たす文字列 $S'$ が存在する場合は Yes を、存在しない場合は No を出力せよ。

题目大意

$T$ 组数据。

每组给定 $N$，$K$ 和长度为 $N$ 的字符串 $S$，求是否能构造一个长度为 $K$ 的字符串 $V$，使得 $VS$ 和$SV$ 都为回文串。

2
6 2
abbaab
5 3
abcbb

Yes
No

3
12 400378271514996652
njvhhvjnnjvh
10 884633988115575508
rrhiyvrrur
36 71630165869626180
vsxmxajrrduhhudrrjaxmxsvvsxmxajrrduh

Yes
No
Yes

提示

制約

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

Sample Explanation 1

$1$ 番目のテストケースについて、例えば $S'\ =\ {}$ba とすると $S,S'$ をこの順に結合して得られる文字列 abbaabba は回文になっています。また、 $S',S$ をこの順に結合して得られる文字列 baabbaab も回文になっています。以上より $S'\ =\ {}$ba は条件を満たすので答えは Yes になります。 $2$ 番目のテストケースについては、条件を満たす $S'$ が存在しないことが証明できます。