Skier rides on a snowy field. Its movements can be described by a string of characters 'S', 'N', 'W', 'E' (which correspond to 1 meter movement in the south, north, west or east direction respectively).

It is known that if he moves along a previously unvisited segment of a path (i.e. this segment of the path is visited the first time), then the time of such movement is 5 seconds. If he rolls along previously visited segment of a path (i.e., this segment of the path has been covered by his path before), then it takes 1 second.

Find the skier's time to roll all the path.

Input

The first line contains an integer t (1 ≤ t ≤ 10^4) — the number of test cases in the input. Then t test cases follow.

Each set is given by one nonempty string of the characters 'S', 'N', 'W', 'E'. The length of the string does not exceed 10^5 characters.

The sum of the lengths of t given lines over all test cases in the input does not exceed 10^5.

Output

For each test case, print the desired path time in seconds.

Example

Input


5
NNN
NS
WWEN
WWEE
NWNWS


Output


15
6
16
12
25
#include <bits/stdc++.h>
using namespace std;
long long int combi(long long int n, long long int k) {
  long long int ans = 1;
  k = k > n - k ? n - k : k;
  long long int j = 1;
  for (; j <= k; j++, n--) {
    if (n % j == 0) {
      ans *= n / j;
    } else if (ans % j == 0) {
      ans = ans / j * n;
    } else {
      ans = (ans * n) / j;
    }
  }
  return ans;
}
long long int gcd(long long int a, long long int b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
long long int findlcm(vector<long long int> arr, long long int n) {
  long long int ans = arr[0];
  for (long long int i = 1; i < n; i++)
    ans = (((arr[i] * ans)) / (gcd(arr[i], ans)));
  return ans;
}
long long int power(long long int x, long long int y, long long int p) {
  long long int 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() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  long long int t;
  cin >> t;
  while (t--) {
    set<pair<pair<long long int, long long int>,
             pair<long long int, long long int> > >
        st;
    string s;
    cin >> s;
    if (s.length() > 0) {
      long long int time = 0;
      long long int x = 0, y = 0;
      time += 5;
      if (s[0] == 'N')
        y++;
      else if (s[0] == 'S')
        y--;
      else if (s[0] == 'E')
        x++;
      else if (s[0] == 'W')
        x--;
      st.insert(make_pair(make_pair(0, 0), make_pair(x, y)));
      long long int j = 1;
      long long int prev_x = x, prev_y = y;
      while (j < s.length()) {
        if (s[j] == 'N')
          y++;
        else if (s[j] == 'S')
          y--;
        else if (s[j] == 'E')
          x++;
        else if (s[j] == 'W')
          x--;
        if (st.find({{prev_x, prev_y}, {x, y}}) == st.end() &&
            st.find({{x, y}, {prev_x, prev_y}}) == st.end()) {
          time += 5;
          st.insert(make_pair(make_pair(x, y), make_pair(prev_x, prev_y)));
          st.insert(make_pair(make_pair(prev_x, prev_y), make_pair(x, y)));
        } else
          time++;
        prev_x = x;
        prev_y = y;
        j++;
      }
      cout << time << "\n";
    } else
      cout << "0\n";
  }
  return 0;
}
