A. Serval and String Theory
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

A string $$$r$$$ consisting only of lowercase Latin letters is called universal if and only if $$$r$$$ is lexicographically smaller$$$^{\text{∗}}$$$ than the reversal$$$^{\text{†}}$$$ of $$$r$$$.

You are given a string $$$s$$$ consisting of $$$n$$$ lowercase Latin letters. You are required to make $$$s$$$ universal. To achieve this, you can perform the following operation on $$$s$$$ at most $$$k$$$ times:

  • Choose two indices $$$i$$$ and $$$j$$$ ($$$1\le i,j\le n$$$), then swap $$$s_i$$$ and $$$s_j$$$. Note that if $$$i=j$$$, you do nothing.

Determine whether you can make $$$s$$$ universal by performing the above operation at most $$$k$$$ times.

$$$^{\text{∗}}$$$A string $$$a$$$ is lexicographically smaller than a string $$$b$$$ of the same length, if and only if the following holds:

  • in the first position where $$$a$$$ and $$$b$$$ differ, the string $$$a$$$ has a letter that appears earlier in the alphabet than the corresponding letter in $$$b$$$.

$$$^{\text{†}}$$$The reversal of a string $$$r$$$ is the string obtained by writing $$$r$$$ from right to left. For example, the reversal of the string $$$\texttt{abcad}$$$ is $$$\texttt{dacba}$$$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 500$$$). The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1\le n\le 100$$$, $$$0\le k\le 10^4$$$) — the length of the string $$$s$$$, and the maximum number of operations you can perform.

The second line contains a string $$$s$$$ consisting of $$$n$$$ lowercase Latin letters.

Output

For each test case, print "YES" if it is possible to make $$$s$$$ universal by performing the operation at most $$$k$$$ times. Otherwise, print "NO".

You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.

Example
Input
8
1 10000
a
3 3
rev
6 0
string
6 0
theory
9 2
universal
19 0
codeforcesecrofedoc
19 1
codeforcesecrofedoc
3 1
zzz
Output
NO
YES
NO
YES
YES
NO
YES
NO
Note

In the first test case, $$$s$$$ will keep the same after any operations. However, the reversal of $$$\texttt{a}$$$ is still $$$\texttt{a}$$$, so it is impossible to make $$$s$$$ universal.

In the second test case, the string $$$\texttt{rev}$$$ is lexicographically smaller than $$$\texttt{ver}$$$. Thus, $$$s$$$ is already universal.

In the fifth test case, you can perform the operations as follows:

  1. Swap $$$s_4$$$ and $$$s_7$$$. After this operation, $$$s$$$ becomes $$$\texttt{uniserval}$$$;
  2. Swap $$$s_1$$$ and $$$s_3$$$. After this operation, $$$s$$$ becomes $$$\texttt{inuserval}$$$.

And the string $$$\texttt{inuserval}$$$ is universal.