Given a string $S$ consisting of the first $n$ lowercase letters.
A string $S$ is a factorial string if and only if all permutations (a total of $n!$) of the first $n$ lowercase letters appear as subsequences (not necessarily contiguous) of $S$.
Starting from this definition, one can obtain a simple enumeration method to verify this, but it is too slow. Therefore, please design an algorithm to determine whether a given string is a factorial string within 1 second.
Input
The first line contains an integer $T$, representing the number of test cases in this file.
Following this are $T$ blocks, each consisting of 2 lines:
The first line contains a positive integer $n$, indicating that $S$ consists of the first $n$ lowercase letters.
The second line contains a string $S$.
Output
For each test case, output a single line. Each line should be YES or NO, indicating whether the corresponding string is a factorial string.
Examples
Input 1
2 2 bbaa 2 aba
Output 1
NO YES
Note
In the first test case, the string $ab$ does not appear as a subsequence.
Constraints
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| $n \le$ | 3 | 5 | 20 | 7 | 20 | 20 | 20 | 26 | 26 | 26 | ||
| $T =$ | 4 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | ||
| $ | S | \le$ | 10 | 350 | 400 | 300 | 450 | 450 | 450 | 450 | 450 | 450 |
Table 1. Constraints on n, T, and |S|