855A. Is It a Cat?

You were walking down the street and heard a sound. 

The sound was described by the string s consisting of lowercase and uppercase Latin characters. Now you want to find out if the sound was a cat meowing.

For the sound to be a meowing, the string can only contain the letters 'm', 'e', 'o' and 'w', in either uppercase or lowercase. Also:

• string must start with non-empty sequence consisting only of characters 'm' or 'M'

• it must be immediately followed by non-empty sequence consisting only of characters 'e' or 'E'

• it must be immediately followed by non-empty sequence consisting only of characters 'o' or 'O'

• it must be immediately followed by non-empty sequence consisting only of characters 'w' or 'W', this sequence ends the string, after it immediately comes the string end

For example, strings "meow", "mmmEeOWww", "MeOooOw" describe a meowing, but strings "Mweo", "MeO", "moew", "MmEW", "meowmeow" do not.

Determine whether the sound you heard was a cat meowing or something else.

Input

The first line of input data contains a single integer t (1≤t≤104) — the number of test cases.

The description of the test cases follows.

The first line of each test case contains an integer n (1≤n≤501) — the length of the string describing the sound.

The second line of each test case contains a string s of n characters. The string describes the sound you heard and consists only of lowercase and uppercase Latin letters.

Output

For each test case, output on a separate line:

• YES if the sound was a cat meowing;

• NO otherwise.

You can output YES and NO in any case (for example, strings yEs, yes, Yes and YES will be recognized as positive response).

Example

input

Copy

7

4

meOw

14

mMmeoOoWWWwwwW

3

mew

7

MmeEeUw

4

MEOW

6

MmyaVW

5

meowA

output

Copy

YES YES NO NO YES NO NO

Note

In the first test case, the string consists of a sequence of characters 'm', 'e', 'O', 'w', which satisfies the definition of meowing.

In the second test case, the string consists of a sequence of 33 characters 'm' and 'M', one 'e', a sequence of 33 characters 'o' and 'O' and a sequence of 77 characters 'w' and 'W', which satisfies the definition of meowing.

In the third test case, the string does not describe a meowing because it lacks a sequence of 'o' or 'O' characters between 'e' and 'w'.

In the fourth test case, the string contains the character 'U', so it does not describe a meowing.

1：判断是否是全部包含meow这几个字符，这里使用set

2：判断每个字符出现时候的左边的位置以及右边的位置；

3：每个字符去跟剩下的字符去比对是否已经按照顺序了。

4：如果都符合，才返回true，其他时候，false；

经验教训：set没有用到，其次判断是否存在，我已经用了函数了，但是不管用，就是每个字符出线的左跟右的位置去判断的。