小A很喜欢字母N，他认为连续的N串是他的幸运串。有一天小A看到了一个全部由大写字母组成的字符串，他被允许改变最多2个大写字母（也允许不改变或者只改变1个大写字母），使得字符串中所包含的最长的连续的N串的长度最长。你能帮助他吗？

输入描述:

输入的第一行是一个正整数T（0 < T <= 20），表示有T组测试数据。对于每一个测试数据包含一行大写字符串S（0 < |S| <= 50000，|S|表示字符串长度）。

数据范围：

20%的数据中，字符串长度不超过100；

70%的数据中，字符串长度不超过1000；

100%的数据中，字符串长度不超过50000。

输出描述:

对于每一组测试样例，输出一个整数，表示操作后包含的最长的连续N串的长度。

输入例子1:

3
NNTN
NNNNGGNNNN
NGNNNNGNNNNNNNNSNNNN

输出例子1:

4
10
18

#include <bits/stdc++.h>

using namespace std;

int main(){
    int n;
    cin >> n;
    for (int j = 0; j < n; j++) {
        string s;
        cin >> s;
        int len = 0;
        int i = 0, res = 1;
        if (s.size() >= 2) res = 2;
        vector<int> v;
        while (i < s.size()) {
            while(i < s.size() && s[i] == 'N') {
                i++;
                len++;
            }
            if(len != 0) v.push_back(len);
            len = 0;
            while(i < s.size() && s[i] != 'N') {
                i++;
                len++;
            }
            if(len != 0) v.push_back(len);
            len = 0;
        }
        if (s[0] == 'N') {
            res = v[0];
            i = 1;
        } else {
            i = 0;
        }
        
        for (;i < v.size(); i += 2) {
            if (v[i] == 2) {
                res = max(res, v[i - 1] + 2);
                if(i + 1 < v.size()) {
                    res = max(res, v[i - 1] + 2 + v[i + 1]);
                }
            } else if (v[i] != 2 && v[i] != 1) {
                if(i - 1 >= 0) {
                    res = max(res, v[i - 1]);
                }
                if (i < v.size() - 1) {
                    res = max(res, v[i + 1]);
                }
            } else {
                if (i + 1 < v.size() && i - 1 >= 0) {
                    res = max(res, v[i - 1] + 1 + v[i + 1]);
                    if (i - 2 >= 0){
                        res = max(res, v[i - 1] + 2 + v[i + 1]);
                    }
                }
                if (i - 3 >= 0 && v[i - 2] == 1 && i + 1 < v.size()) {
                    res = max(res, v[i - 1] + v[i + 1] + v[i - 3] + 2);
                }
                if (i - 2 >= 0 && v[i - 2] >= 1) {
                    res = max(res, v[i - 1] + 2);
                }
                
            }
        }

        cout << res << endl;
    }
    return 0;
}