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.

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.

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$.

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

见题面 Input 部分

见题面 Output 部分