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 inf = 1e18;
long long int expo(long long int x, long long int y) {
  long long int ans = 1;
  while (y != 0) {
    if (y % 2) {
      ans = ans * x;
    }
    y = y >> 1;
    x = x * x;
  }
  return ans;
}
long long int gcd(long long int a, long long int b) {
  if (a == 0) return b;
  return gcd(b % a, a);
}
long long int lcm(long long int a, long long int b) {
  return (a * b) / gcd(a, b);
}
long long int max(long long int x, long long int y) {
  if (x > y) return x;
  return y;
}
long long int min(long long int x, long long int y) {
  if (x < y) return x;
  return y;
}
vector<long long int> SieveOfEratosthenes(long long int n) {
  vector<long long int> primes;
  bool prime[n + 1];
  memset(prime, true, sizeof(prime));
  for (long long int p = 2; p * p <= n; p++) {
    if (prime[p] == true) {
      for (long long int i = p * p; i <= n; i += p) prime[i] = false;
    }
  }
  for (long long int p = 2; p <= n; p++)
    if (prime[p]) primes.push_back(p);
  return primes;
}
vector<long long int> getDivisors(long long int num) {
  vector<long long int> divisors;
  for (long long int i = 1; i * i <= num; i++) {
    if (!(num % i)) {
      if (i * i == num)
        divisors.push_back(i);
      else {
        divisors.push_back(i);
        divisors.push_back(num / i);
      }
    }
  }
  sort(divisors.begin(), divisors.end());
  return divisors;
}
void displayVector(vector<long long int> vect) {
  for (long long int i = 0; i < vect.size(); i++) cout << vect[i] << " ";
  cout << endl;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  long long int t;
  cin >> t;
  string s;
  while (t--) {
    cin >> s;
    set<pair<pair<long long int, long long int>,
             pair<long long int, long long int>>>
        paths;
    pair<long long int, long long int> starting_coord = {0, 0};
    pair<long long int, long long int> ending_coord;
    long long int ans = 0;
    for (long long int i = 0; i < s.size(); i++) {
      if (s[i] == 'N')
        ending_coord = {starting_coord.first, starting_coord.second + 1};
      if (s[i] == 'E')
        ending_coord = {starting_coord.first + 1, starting_coord.second};
      if (s[i] == 'S')
        ending_coord = {starting_coord.first, starting_coord.second - 1};
      if (s[i] == 'W')
        ending_coord = {starting_coord.first - 1, starting_coord.second};
      pair<pair<long long int, long long int>,
           pair<long long int, long long int>>
          new_path1 = {{starting_coord.first, starting_coord.second},
                       {ending_coord.first, ending_coord.second}};
      pair<pair<long long int, long long int>,
           pair<long long int, long long int>>
          new_path2 = {{ending_coord.first, ending_coord.second},
                       {starting_coord.first, starting_coord.second}};
      starting_coord = {ending_coord.first, ending_coord.second};
      if (paths.find(new_path1) == paths.end() &&
          paths.find(new_path2) == paths.end()) {
        ans += 5;
        paths.insert(new_path1);
      } else {
        ans += 1;
      }
    }
    cout << ans << endl;
  }
}
