Nasser's String - Repovive Starter Round 5 | Repovive

17A. Nasser's String

500 pts1s256 MB

Nasser gives you a string $s$ of length $n$ consisting of lowercase English letters.

In one operation, you can swap any two adjacent characters in the string.

Your task is to determine if it is possible to obtain at least one substring equal to "nasser" after performing any number of such operations (possibly zero).

A substring is a contiguous segment of the string.

Input

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

The first line of each test case contains an integer $n$ $(1 \le n \le 2 \cdot 10^5)$ - the length of the string.

The second line of each test case contains a string $s$ of length $n$ , consisting of lowercase English letters.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$ .

Output

For each test case, output "Yes" if it is possible to obtain a substring equal to "nasser", otherwise output "No".

Samples

Input

Case 1

6
assern

Case 2

6
naspas

Explanation

In the first test case, $s=$ "assern":

We can swap adjacent characters to rearrange "assern" into "nasser".
Since the entire string becomes "nasser", it contains "nasser" as a substring.
Answer: "Yes".

Output

Case 1

Yes

Case 2

No

Nasser gives you a string $s$ of length $n$ consisting of lowercase English letters.

In one operation, you can swap any two adjacent characters in the string.

Your task is to determine if it is possible to obtain at least one substring equal to "nasser" after performing any number of such operations (possibly zero).

A substring is a contiguous segment of the string.

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

The first line of each test case contains an integer $n$ $(1 \le n \le 2 \cdot 10^5)$ - the length of the string.

The second line of each test case contains a string $s$ of length $n$ , consisting of lowercase English letters.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$ .

In the first test case, $s=$ "assern":

We can swap adjacent characters to rearrange "assern" into "nasser".
Since the entire string becomes "nasser", it contains "nasser" as a substring.
Answer: "Yes".

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

17A. Nasser's String

Input

Output

Samples

17A. Nasser's String

Input

Output

Samples