H. Substring Game
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Given a string $$$s$$$, two players Hiraethsoul and hjh play the following game:

  • Initially, both players have empty strings $$$a$$$ and $$$b$$$.
  • The two players take turns, and Hiraethsoul moves first.
  • In each move, the current player removes exactly one character from either the front or the back of string $$$s$$$.
  • The removed character is appended to the end of the player's own string.
  • The game ends when $$$s$$$ becomes empty.

After the game ends:

  • If string $$$a$$$ contains the substring "scut", then Hiraethsoul wins.
  • Otherwise, hjh wins.

Determine the winner assuming both players play optimally.

Input

The first line contains a single integer $$$q$$$ ($$$1 \le q \le 5 \times 10^4$$$), the number of test cases.

For each test case:

The first line contains a single integer $$$n$$$ ($$$1 \le n \le 10^4$$$), the length of the string.

The second line contains a string $$$s$$$ of length $$$n$$$, consisting only of lowercase letters s, c, u, and t.

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

Output

For each test case, print Yes if Hiraethsoul wins; otherwise print No.

Example
Input
2
7
scuttuc
5
scuts
Output
Yes
No
Note

Players always append the chosen character to the end of their own string. The substring condition is checked only after the game ends. A substring is defined as a contiguous sequence of characters within a string.