C. Alternet is Cheating
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Disclaimer: the only part about this statement that is real is the part where I lose against all real participants. — Alternet

lethan3 is organizing a lockout tournament!

lethan3 has a tournament of $$$N$$$ participants ($$$N$$$ is a power of 2). The tournament follows a specific match format: participant 1 plays against participant 2, participant 3 plays against participant 4, and so on. After the round, the losers step out of the tournament and the winners progress to the next round in the same order. In the second round, the winner of match 1 and the winner of match 2 play against each other, and similarly, the winners of matches 3 and 4 play against each other, etc. Rounds are played until there is only one winner left.

Alternet is participating in lethan3's lockout tournament. Unfortunately for him, he has no skill and is dominated by all of the participants. Fortunately, he has many friends (also in the tournament) who will help him win. Because Alternet knows the order in which participants will solve problems, he can instruct his friends to snipe them.

Formally:

There are three types of participants: real participants, Alternet's friends, and Alternet.

When two real participants compete, the one with a lower seed wins (The $$$i$$$th participant has seed $$$i$$$).

Alternet can teach each one of his friends individually to beat exactly one real participant (they will lose to all other real participants). Alternet's friends will let Alternet win against them, and when Alternet's friends compete against each other, Alternet can decide who wins.

Alternet loses against real participants and only wins against his friends.

Alternet really wants to win the tournament. So, he asks you to determine if it's possible to win the tournament.

Input

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

For each test case:

The first line contains one integer $$$N$$$ ($$$2 \leq N \le 2^{10} = 1024$$$.)

The following line contains a string of length $$$N$$$. The $$$i$$$th character indicates if the $$$i$$$th participant is a real participant ("R"), one of Alternet's friends ("F"), or Alternet ("A"). It is guaranteed that there is one and only one Alternet in each test case.

—

There are $$$20$$$ tests (with samples skipped). Each test is worth $$$\frac{100}{20} = 5$$$ points.

Output

For each test case, print "Yes" if Alternet is able to win and "No" otherwise.

Example
Input
3
2
AR
4
RFAF
4
RRAF
Output
No
Yes
No
Note

In the first test case, Alternet immediately loses to the real participant.

In the second test case, Alternet can win if both of his friends are taught to defeat the only real participant.

In the third test case, it can be proven that Alternet cannot win the tournament.

—

Problem Idea: alternet

Problem Preperation: alternet

Occurrences: Novice 3