C. Skier

Skier rides on a snowy field. Its movements can be described by a string of characters 'S', 'N', 'W', 'E' (which correspond to 11 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 55 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 11 second.

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

Input

The first line contains an integer tt (1≤t≤1041≤t≤104) — the number of test cases in the input. Then tt 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 105105 characters.

The sum of the lengths of tt given lines over all test cases in the input does not exceed 105105.

Output

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

Example

input

Copy

5
NNN
NS
WWEN
WWEE
NWNWS

output

Copy

15
6
16
12
25

结构体作为map、set等容器的键值时，需重载 < 号，重载时注意使用 if 、else if 、else 重载

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-12;
const double PI = acos(-1.0);
const int N = 2e5 + 5;

struct node
{
    int x1, y1, x2, y2;
    node(){};
    node(int xx1, int yy1, int xx2, int yy2):x1(xx1), y1(yy1), x2(xx2), y2(yy2){}
    bool operator < (const node &a)const
    {
        if(x1 != a.x1)
            return x1 > a.x1;
        else if(y1 != a.y1)
            return y1 > a.y1;
        else if(x2 != a.x2)
            return x2 > a.x2;
        else
            return y2 > a.y2;
    }
};

int main()
{
    int t;
    string s;
    scanf("%d", &t);
    while(t--)
    {
        cin >> s;
        int len = s.size();
        map<node, int>mp;
        int prex = 0;
        int prey = 0;
        int x = 0;
        int y = 0;
        int cnt = 0;
        for(int i = 0; i < len; ++i)
        {
            switch(s[i])
            {
            case 'N':
                y++;
                break;
            case 'S':
                y--;
                break;
            case 'E':
                x++;
                break;
            case 'W':
                x--;
                break;
            }
            if(mp.count(node(prex, prey, x, y)))
            {
                cnt++;
            }
            else
            {
                mp[node(prex, prey, x, y)]++;
                mp[node(x, y, prex, prey)]++;
            }
            prex = x;
            prey = y;
        }
        cout<<cnt + (len - cnt) * 5<<'\n';
    }
    return 0;
}