Problem Statement

You are given a string $S$ of length $N$ consisting of lowercase English letters, and a positive integer $K$.

Determine whether there is a string $S'$ of length $K$ that satisfies the following conditions.

• The concatenation of $S$ and $S'$ in this order is a palindrome.
• The concatenation of $S'$ and $S$ in this order is a palindrome.

You have $T$ test cases to solve.

Constraints

• $1 \\leq T \\leq 10^5$
• $1 \\leq N \\leq 2 \\times 10^5$
• $1 \\leq K \\leq 10^{18}$
• $S$ is a string of length $N$ consisting of lowercase English letters.
• All numbers in the input are integers.
• In each input file, the sum of $N$ over the test cases is at most $2 \\times 10^5$.

Input

The input is given from Standard Input in the following format:

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

Each case is in the following format:

$N$ $K$ $S$

Output

Print $T$ lines. The $i$-th line should contain Yes if there is a string $S'$ that satisfies the conditions for the $i$-th test case, and No otherwise.

Sample Input 1

2
6 2
abbaab
5 3
abcbb

Sample Output 1

Yes
No

For the first test case, if we let $S' = {}$ba, for instance, the concatenation of $S$ and $S'$ in this order will be abbaabba, which is a palindrome. Here, the concatenation of $S'$ and $S$ in this order is baabbaab, which is also a palindrome. Thus, $S' = {}$ba satisfies the condition, so the answer is Yes.

For the second test case, we can prove that no string satisfies the conditions.

Sample Input 2

3
12 400378271514996652
njvhhvjnnjvh
10 884633988115575508
rrhiyvrrur
36 71630165869626180
vsxmxajrrduhhudrrjaxmxsvvsxmxajrrduh

Sample Output 2

Yes
No
Yes