C. Unique Subsequences
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a string $$$s$$$ of length $$$n$$$. Determine if all subsequences of $$$s$$$ that have length $$$k$$$ are unique.

A subsequence of $$$s$$$ is defined as a sequence that can be obtained from $$$s$$$ by deleting some elements (possibly none), without changing the order of the remaining elements.

For instance, the subsequences of $$$trust$$$ of length $$$4$$$ are $$$trus$$$, $$$trut$$$, $$$trst$$$, and $$$rust$$$, all of which are unique.

But when considering subsequences of $$$threes$$$ of length $$$4$$$. The subsequence $$$tres$$$ occurs twice ($$$\underline{t}h\underline{re}e\underline{s}$$$ and $$$\underline{t}h\underline{r}e\underline{es}$$$).

Input

The first line of input contains a single integer $$$T$$$ denoting the number of test cases $$$(1 \leq T \leq 10^3)$$$.

The first line of each test case contains two integers $$$n \ k$$$ denoting the length of the string and the length of subsequences to consider $$$(1 \leq k \leq n \leq 10^5)$$$.

The second line contains a string $$$s$$$ of length $$$n$$$ consisting only of lowercase English letters.

It is guaranteed that the sum of $$$n$$$ across all test cases does not exceed $$$3 \cdot 10^5$$$.

—

Tests in subtasks are numbered from $$$1 - 10$$$ with samples skipped. Each test is worth $$$\frac{100}{10} = 10$$$ points.

Tests $$$1 - 3$$$ satisfy $$$n \leq 10$$$.

Tests $$$4 - 5$$$ satisfy that the sum of $$$n$$$ across all test cases does not exceed $$$3366$$$.

The remaining tests do not satisfy any additional constraints.

Output

For each test case, output "Yes" (without the quotes) if all subsequences of length $$$k$$$ are unique or "No" (without the quotes) otherwise.

Example
Input
11
5 4
trust
6 4
threes
6 4
abcdba
8 4
sendhelp
9 8
imtrapped
7 6
inabase
9 5
mentuntil
7 1
ifinish
9 7
preparing
8 3
problems
8 8
heeeeelp
Output
Yes
No
Yes
No
No
Yes
No
No
Yes
Yes
Yes
Note

It can be proven that all $$$15$$$ subsequences of length $$$4$$$ of $$$abcdba$$$ are unique (by listing them out and reading over them carefully). Also I'm trapped in Tho$$$[$$$deleted$$$]$$$

—

Problem Idea: dutin

Problem Preperation: 3366

Occurrences: Novice 6, Advanced 3