The FB-string is formed as follows. Initially, it is empty. We go through all positive integers, starting from $1$, in ascending order, and do the following for each integer:

• if the current integer is divisible by $3$, append F to the end of the FB-string;
• if the current integer is divisible by $5$, append B to the end of the FB-string.

Note that if an integer is divisible by both $3$ and $5$, we append F, and then B, not in the opposite order.

The first $10$ characters of the FB-string are FBFFBFFBFB: the first F comes from the integer $3$, the next character (B) comes from $5$, the next F comes from the integer $6$, and so on. It's easy to see that this string is infinitely long. Let $f_i$ be the $i$-th character of FB-string; so, $f_1$ is F, $f_2$ is B, $f_3$ is F, $f_4$ is F, and so on.

You are given a string $s$, consisting of characters F and/or B. You have to determine whether it is a substring (contiguous subsequence) of the FB-string. In other words, determine if it is possible to choose two integers $l$ and $r$ ($1 \le l \le r$) so that the string $f_l f_{l+1} f_{l+2} \dots f_r$ is exactly $s$.

For example:

• FFB is a substring of the FB-string: if we pick $l = 3$ and $r = 5$, the string $f_3 f_4 f_5$ is exactly FFB;
• BFFBFFBF is a substring of the FB-string: if we pick $l = 2$ and $r = 9$, the string $f_2 f_3 f_4 \dots f_9$ is exactly BFFBFFBF;
• BBB is not a substring of the FB-string.

Input

The first line contains one integer $t$ ($1 \le t \le 2046$) — the number of test cases.

Each test case consists of two lines. The first line contains one integer $k$ ($1 \le k \le 10$) — the number of characters in $s$. The second line contains $s$, which is a string of exactly $k$ characters. Each character of $s$ is either F or B.

Output

For each test case, print YES if $s$ is a substring of the FB-string, or NO otherwise.

You may print each letter in any case (YES, yes, Yes will all be recognized as positive answer, NO, no and nO will all be recognized as negative answer).

Samples

3
3
FFB
8
BFFBFFBF
3
BBB

YES
YES
NO