Description

Given a string $S$ composed of the first $n$ lowercase letters. The string $S$ is a factorial string if and only if every permutation of the first $n$ lowercase letters (in total $n!$ permutations) appears as a subsequence (not necessarily contiguous).

From this definition, a simple enumeration can be used to verify it, but it is far too slow. Please design an algorithm to determine within $1$ second whether the given string is a factorial string.

Input Format

The first line contains an integer $T$, indicating that there are $T$ test cases in this file.

Then $T$ blocks follow, each with $2$ lines:

• Line $1$: a positive integer $n$, indicating that $S$ is composed of the first $n$ lowercase letters.
• Line $2$: a string $s$.

Output Format

For each test case, output one line: YES or NO, indicating whether the corresponding string $S$ is a factorial string.

2
2
bbaa
2
aba

NO
YES

Hint

In the first test case, the string ab does not appear as a subsequence.

Translated by ChatGPT 5