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;
void error(istream_iterator<string> _iterat) {}
template <typename T, typename... args>
void error(istream_iterator<string> _iterat, T a, args... arguments) {
  cerr << *_iterat << "=" << a << "\n";
  error(++_iterat, arguments...);
}
template <typename T, typename V>
void error(string pri, const pair<T, V> &z) {
  cerr << pri << "="
       << "{" << z.first << "," << z.second << "}"
       << "\n";
}
template <typename T, typename V>
void error(string pri, const map<T, V> &z) {
  cerr << pri << " is={";
  for (auto it = z.begin(); it != z.end(); ++it) {
    cerr << it->first << ":" << it->second;
    auto _it = z.end();
    _it--;
    if (it != _it) cerr << ",";
  }
  cerr << "}";
  cerr << "\n";
}
template <typename T>
void error(string pri, const vector<T> &z, long long st, long long ed) {
  cerr << pri << " in range[" << st << "," << ed << ")=[";
  for (long long i = st; i < ed; ++i) {
    cerr << z[i];
    if (i != ed - 1) cerr << " ";
  }
  cerr << "]";
  cerr << "\n";
}
template <typename T>
void error(string pri, const set<T> &z, long long st, long long ed) {
  cerr << pri << " in range[" << st << "," << ed << ")=[";
  long long tempcount = 0;
  for (auto it = z.begin(); it != z.end(); ++it) {
    if (tempcount >= st and tempcount < ed) {
      cerr << *it;
      if (tempcount != ed - 1) cerr << " ";
    }
    tempcount++;
  }
  cerr << "]";
  cerr << "\n";
}
template <typename T>
void error(string pri, const T z[], long long st, long long ed) {
  cerr << pri << " in range[" << st << "," << ed << ")=[";
  for (long long i = st; i < ed; ++i) {
    cerr << z[i];
    if (i != ed - 1) cerr << " ";
  }
  cerr << "]";
  cerr << "\n";
}
void logic() {
  string s;
  cin >> s;
  int x = 0;
  int y = 0;
  unordered_map<string, bool> m;
  int n = s.length();
  int ans = 0;
  for (int i = 0; i < n; ++i) {
    int temp1 = x;
    int temp2 = y;
    if (s[i] == 'N')
      y++;
    else if (s[i] == 'S')
      y--;
    else if (s[i] == 'E')
      x++;
    else if (s[i] == 'W')
      x--;
    string s1 = "\0";
    string s2 = "\0";
    s1 = s1 + to_string(temp1) + '-' + to_string(temp2) + '-' + to_string(x) +
         '-' + to_string(y);
    s2 = s2 + to_string(x) + '-' + to_string(y) + '-' + to_string(temp1) + '-' +
         to_string(temp2);
    if (m[s1] == 1 or m[s2] == 1)
      ans = ans + 1;
    else {
      m[s1] = 1;
      ans = ans + 5;
    }
  }
  cout << ans;
  cout << "\n";
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  long long t;
  cin >> t;
  while (t--) {
    logic();
  }
}
