Rearrange Substrings

You are given a string s and a positive integer k. Your task is to determine whether there exists a rearrangement of the characters of s such that every contiguous substring of length k contains at least k-1 distinct characters.

More formally, let n be the length of s and let f represent the maximum frequency of any character in s (i.e. \( f = \max_{c} \text{count}(c) \)). A necessary (and in this problem, sufficient) condition for such a rearrangement to exist is: $$ f \leq n - (k-1) \times (f-1). $$ If the condition is satisfied, output Yes; otherwise, output No.

Note: When k = 1, every substring of length 1 is trivially valid, so the answer is always Yes.

inputFormat

The first line of input contains a single integer t, the number of test cases. Each test case consists of two lines:

• The first line contains an integer k.
• The second line contains the string s.

You need to process all t test cases.

outputFormat

For each test case, output a single line containing Yes if a valid rearrangement exists and No otherwise.

## sample

3
3
aabbcc
2
aabb
4
aaaabbbb

Yes
Yes
No

</p>