题目描述

给定一个由小写英文字母组成、长度为 $N$ 的字符串 $S$，以及一个正整数 $K$。

请判断是否存在一个长度为 $K$ 的字符串 $S'$，使得以下条件都成立：

• 将 $S$ 和 $S'$ 按顺序连接得到的字符串是回文串。
• 将 $S'$ 和 $S$ 按顺序连接得到的字符串是回文串。

有 $T$ 组测试数据，请分别判断每组数据。

输入格式

输入以如下格式从标准输入读入。

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

每组数据格式如下：

$N\ K\ S$

输出格式

输出 $T$ 行。对于第 $i$ 组测试数据，如果存在满足条件的字符串 $S'$，则输出 Yes，否则输出 No。

样例 1

输入

2
6 2
abbaab
5 3
abcbb

输出

Yes
No

样例 2

输入

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$ 的字符串
• 输入的所有数值均为整数
• 所有测试数据中 $N$ 的总和不超过 $2 \times 10^5$

样例解释 1

对于第 $1$ 组测试数据，例如取 $S' =$ba，则 $S,S'$ 按顺序连接得到的字符串 abbaabba 是回文串。同时，$S',S$ 按顺序连接得到的字符串 baabbaab 也是回文串。因此 $S' =$ba 满足条件，答案为 Yes。对于第 $2$ 组测试数据，可以证明不存在满足条件的 $S'$。

由 ChatGPT 4.1 翻译