#include <bits/stdc++.h>
using namespace std;
long long power(long long x, long long y, long long p) {
  long long res = 1;
  x = x % p;
  if (x == 0) return 0;
  while (y > 0) {
    if (y & 1) res = (res * x) % p;
    y = y >> 1;
    x = (x * x) % p;
  }
  return res;
}
int main() {
  long long t = 0;
  string s;
  cin >> t;
  for (long long i = 0; i < t; i++) {
    cin >> s;
    long long n = s.length();
    if (s[n - 1] == 'E') {
      long long c = 0;
      for (long long j = 0; j < n; j++) {
        if (s[j] == 'N') c++;
      }
      if (c != 1)
        cout << "YES" << endl;
      else
        cout << "NO" << endl;
    } else {
      long long f = 0;
      for (long long j = 0; j < n - 1; j++) {
        if (s[j] == 'N') {
          f = 1;
          break;
        }
      }
      if (f == 1)
        cout << "YES" << endl;
      else
        cout << "NO" << endl;
    }
  }
}

### Prompt

Please create a solution in CPP to the following problem:

You had n positive integers a_1, a_2, ..., a_n arranged in a circle. For each pair of neighboring numbers (a_1 and a_2, a_2 and a_3, ..., a_{n - 1} and a_n, and a_n and a_1), you wrote down: are the numbers in the pair equal or not.

Unfortunately, you've lost a piece of paper with the array a. Moreover, you are afraid that even information about equality of neighboring elements may be inconsistent. So, you are wondering: is there any array a which is consistent with information you have about equality or non-equality of corresponding pairs?

Input

The first line contains a single integer t (1 ≤ t ≤ 1000) — the number of test cases. Next t cases follow.

The first and only line of each test case contains a non-empty string s consisting of characters E and/or N. The length of s is equal to the size of array n and 2 ≤ n ≤ 50. For each i from 1 to n: 

  * if s_i = E then a_i is equal to a_{i + 1} (a_n = a_1 for i = n); 
  * if s_i = N then a_i is not equal to a_{i + 1} (a_n ≠ a_1 for i = n). 

Output

For each test case, print YES if it's possible to choose array a that are consistent with information from s you know. Otherwise, print NO.

It can be proved, that if there exists some array a, then there exists an array a of positive integers with values less or equal to 10^9.

Example

Input


4
EEE
EN
ENNEENE
NENN


Output


YES
NO
YES
YES

Note

In the first test case, you can choose, for example, a_1 = a_2 = a_3 = 5.

In the second test case, there is no array a, since, according to s_1, a_1 is equal to a_2, but, according to s_2, a_2 is not equal to a_1.

In the third test case, you can, for example, choose array a = [20, 20, 4, 50, 50, 50, 20].

In the fourth test case, you can, for example, choose a = [1, 3, 3, 7].

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
long long power(long long x, long long y, long long p) {
  long long res = 1;
  x = x % p;
  if (x == 0) return 0;
  while (y > 0) {
    if (y & 1) res = (res * x) % p;
    y = y >> 1;
    x = (x * x) % p;
  }
  return res;
}
int main() {
  long long t = 0;
  string s;
  cin >> t;
  for (long long i = 0; i < t; i++) {
    cin >> s;
    long long n = s.length();
    if (s[n - 1] == 'E') {
      long long c = 0;
      for (long long j = 0; j < n; j++) {
        if (s[j] == 'N') c++;
      }
      if (c != 1)
        cout << "YES" << endl;
      else
        cout << "NO" << endl;
    } else {
      long long f = 0;
      for (long long j = 0; j < n - 1; j++) {
        if (s[j] == 'N') {
          f = 1;
          break;
        }
      }
      if (f == 1)
        cout << "YES" << endl;
      else
        cout << "NO" << endl;
    }
  }
}

```