You will be given a string consisting of lowercase English alphabet. Some characters of this string are missing, we would like to know if it is possible to fill those characters with any lowercase letter so that there is a sub-string that contains exactly \(x\) times each character of English alphabet.
The input start with one line containing one integer denoting the number of test cases. Each test case consists of a line containing an integer \(x\) (\(1 \leq x \leq 10^5\)) and a string S (\( 1 \leq |S| \leq 10^5\), S contains only lowercase English alphabet or a question mark ('?'). A question mark indicates a missing character.)
For each test case output one line containing "YES" (without the quotes) if it's possible to have a substring that contains exactly \(x\) times each character of the English alphabet. Otherwise output "NO".
- (\( 1 \leq x, |S| \leq 100\)), 10 points
- (\( 1 \leq x, |S| \leq 1000\)), 30 points
- (\( 1 \leq x, |S| \leq 100000\)), 60 points
2 2 azertyuiopqsdfghjklmwxcvb??????????????????????????? 1 abcdefghijkllmnopqrstuvwxyz