Cats are attracted to pspspsps, but Evirir, being a dignified dragon, is only attracted to pspspsps with oddly specific requirements...

Given a string $s = s_1s_2\ldots s_n$ of length $n$ consisting of characters p, s, and . (dot), determine whether a permutation$^{\text{∗}}$ $p$ of length $n$ exists, such that for all integers $i$ ($1 \le i \le n$):

• If $s_i$ is p, then $[p_1, p_2, \ldots, p_i]$ forms a permutation (of length $i$);
• If $s_i$ is s, then $[p_i, p_{i+1}, \ldots, p_{n}]$ forms a permutation (of length $n-i+1$);
• If $s_i$ is ., then there is no additional restriction.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \le n \le 500$), the length of $s$.

The second line of each test case contains a string $s$ of length $n$ that consists of the characters p, s, and ..

It is guaranteed that the sum of $n$ over all test cases does not exceed $5000$.

Output

For each test case, output YES or NO on a line. Output YES if there is such a permutation and NO otherwise.

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.

见题面 Input 部分

见题面 Output 部分

For the first test case, one permutation that works is $p = [3, 4, 1, 2]$. The restrictions are as follows:

• $s_1 =$ s: $[p_1, p_2, p_3, p_4] = [3, 4, 1, 2]$ forms a permutation.
• $s_2 =$ .: No additional restriction.
• $s_3 =$ s: $[p_3, p_4] = [1, 2]$ forms a permutation.
• $s_4 =$ p: $[p_1, p_2, p_3, p_4] = [3, 4, 1, 2]$ forms a permutation.

For the second test case, it can be proven that there is no permutation that satisfies all restrictions.

For the third test case, one permutation that satisfies the constraints is $p = [1, 2, 3, 4, 5]$.