AksLolCoding is playing a game on a string $s$ of length $n$. Initially, $s$ contains only lowercase Latin characters.

In one turn, AksLolCoding can choose any pair of integers $(i,j)$ such that:

• $1 \leq i \lt j \leq n$;
• $s_i = s_j \neq *$; and
• $s_k = *$ for all $i \lt k \lt j$.

If no such $i,j$ exists, then the game ends. Otherwise, AksLolCoding sets $s_i:=*$ and $s_j:=*$.

Once the game ends, AksLolCoding wins if and only if every character in $s$ is equal to $*$. Determine if it is possible for AksLolCoding to win.

Note: $*$ represents ASCII character 42.

Input

The first line contains an integer $t$ ($1 \leq t \leq 100$), the number of test cases.

The first line of each test case contains an integer $n$ ($1 \leq n \leq 5000$), the length of the string.

The second line of each test case contains a string $s$ consisting of lowercase Latin characters.

The sum of $n$ over all test cases does not exceed $5000$.

Output

Output the answer to each test case on its own line. If AksLolCoding can win, output "YES" (without quotes). Else, output "NO" (without quotes).

You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.

Note

In the first test case, it can be shown that it is impossible for AksLolCoding to win.

In the second test case, AksLolCoding can win by making the following moves: llmllm $\rightarrow$ llm\*\*m $\rightarrow$ \*\*m\*\*m $\rightarrow$ \*\*\*\*\*\*

In the third test case, AksLolCoding can win by making the following moves: uwuuwu $\rightarrow$ uw\*\*wu $\rightarrow$ u\*\*\*\*u $\rightarrow$ \*\*\*\*\*\*

Samples

6
1
a
6
llmllm
6
uwuuwu
6
byebye
6
oooioi
12
siixxsevvenn

NO
YES
YES
NO
NO
YES