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;
inline int add(int a, int b) {
  a += b;
  return a >= 1000000007 ? a - 1000000007 : a;
}
inline int sub(int a, int b) {
  a -= b;
  return a < 0 ? a + 1000000007 : a;
}
inline int mul(int a, int b) { return (long long int)a * b % 1000000007; }
int Set(int N, int pos) { return N = N | (1 << pos); }
int Reset(int N, int pos) { return N = N & ~(1 << pos); }
bool Cheek(int N, int pos) { return (bool)(N & (1 << pos)); }
const int fx[] = {+1, -1, +0, +0};
const int fy[] = {+0, +0, +1, -1};
struct info {
  int x1, y1, x2, y2;
  info() {}
  info(int a, int b, int c, int d) {
    x1 = a;
    y1 = b;
    x2 = c;
    y2 = d;
  }
  bool operator<(const info &p) const {
    if (x1 != p.x1)
      return x1 < p.x1;
    else if (x2 != p.x2)
      return x2 < p.x2;
    else if (y1 != p.y1)
      return y1 < p.y1;
    else
      return y2 < p.y2;
  }
};
void Solve(int t) {
  int i, j, k, n, ans = 0, xx = 0, yy = 0, nx, ny;
  string s;
  cin >> s;
  n = (int)s.size();
  map<info, int> m;
  for (i = 0; i < n; i++) {
    if (s[i] == 'N') {
      nx = xx + fx[1];
      ny = yy + fy[1];
    } else if (s[i] == 'S') {
      nx = xx + fx[0];
      ny = yy + fy[0];
    } else if (s[i] == 'E') {
      nx = xx + fx[2];
      ny = yy + fy[2];
    } else {
      nx = xx + fx[3];
      ny = yy + fy[3];
    }
    info temp1 = info(xx, yy, nx, ny);
    info temp2 = info(nx, ny, xx, yy);
    if (m[temp1] == 0)
      ans += 5;
    else
      ans += 1;
    m[temp1]++;
    m[temp2]++;
    xx = nx;
    yy = ny;
  }
  cout << ans << endl;
}
int main() {
  int t, T;
  T = 1;
  scanf("%d", &(T));
  for (__typeof(t) t = 1; t <= T; t++) {
    Solve(t);
  }
  return 0;
}
