题目描述

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

判断是否存在一个长度为 $K$ 的字符串 $S'$ 满足以下条件：

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

你需要解决 $T$ 个测试用例。

约束条件

• $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$。

输入格式

输入从标准输入中按以下格式给出：

$T$ $case_1$ $\vdots$ $case_T$

每个测试用例的格式如下：

$N$ $K$ $S$

输出格式

打印 $T$ 行。第 $i$ 行应该包含 Yes 表示对于第 $i$ 个测试用例存在满足条件的字符串 $S'$，或者 No 表示不存在满足条件的字符串 $S'$。

样例输入 1

2
6 2
abbaab
5 3
abcbb

样例输出 1

Yes
No

对于第一个测试用例，如果我们令 $S' = {}$ba，则按顺序拼接得到的字符串为 abbaabba，是一个回文串。同时，按顺序拼接 $S'$ 和 $S$ 得到的字符串为 baabbaab，也是一个回文串。因此，$S' = {}$ba 满足条件，所以答案是 Yes。

对于第二个测试用例，我们可以证明不存在满足条件的字符串。

样例输入 2

3
12 400378271514996652
njvhhvjnnjvh
10 884633988115575508
rrhiyvrrur
36 71630165869626180
vsxmxajrrduhhudrrjaxmxsvvsxmxajrrduh

样例输出 2

Yes
No
Yes