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;
const double pi = acos(-1.0);
const long long mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
struct mmp {
  int x, y, x1, y1;
  bool operator<(const mmp &a) const {
    return (x < a.x || x == a.x && y < a.y ||
            x == a.x && y == a.y && x1 < a.x1 ||
            x == a.x && y == a.y && x1 == a.x1 && y1 < a.y1);
  }
} zz, zzz;
map<mmp, int> z;
char xx[100005];
int main() {
  int a, b, c, d;
  scanf("%d", &d);
  while (d--) {
    scanf("%s", xx);
    b = strlen(xx);
    z.clear();
    a = 0;
    zz.x = 0;
    zz.y = 0;
    zz.x1 = 0;
    zz.y1 = 0;
    for (int i = 0; i < b; i++) {
      zz.x = zz.x1;
      zz.y = zz.y1;
      if (xx[i] == 'N')
        zz.y1++;
      else if (xx[i] == 'E')
        zz.x1++;
      else if (xx[i] == 'S')
        zz.y1--;
      else if (xx[i] == 'W')
        zz.x1--;
      zzz.x = zz.x1;
      zzz.y = zz.y1;
      zzz.x1 = zz.x;
      zzz.y1 = zz.y;
      if (z[zz] == 1)
        a += 1;
      else
        a += 5;
      z[zz] = 1;
      z[zzz] = 1;
    }
    printf("%d\n", a);
  }
}
