K. Abushogi's Happy Name
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Abushogi has recently picked up a fascinating new hobby: analyzing people's names mathematically.First, he takes a person's name (which consists only of lowercase English letters) and converts each character into a number based on its position in the alphabet.

Specifically, 'a' becomes $$$1$$$, 'b' becomes $$$2$$$, 'c' becomes $$$3$$$, and so on, up to 'z' which becomes $$$26$$$. Then, he calculates the product of all these numbers.

Abushogi will be happy if the resulting product is divisible by $$$6$$$. Given a name, determine if Abushogi will be happy.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — the length of the name.

The second line of each test case contains a string $$$s$$$ of length $$$n$$$ consisting of lowercase English letters — the name Abushogi is analyzing.

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 Abushogi will be happy, and "NO" otherwise.

In the output, the "YES"s and "NO"s are case-insensitive, meaning that outputs such as "yEs" and "nO" are valid. However, the grid is case-sensitive.

Example
Input
5
3
abc
4
moon
2
ac
5
aaaaa
4
code
Output
YES
YES
NO
NO
YES
Note

Note: In the first testcase, 'a'=1, 'b'=2, 'c'=3. The product is 6, which is divisible by 6.

In the third testcase, 'a'=1, 'c'=3. The product is 3, which is not divisible by 6. In the fourth testcase, the product is 1