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

输入描述:

输入的第一行是一个正整数T（0 数据范围：20%的数据中，字符串长度不超过100；70%的数据中，字符串长度不超过1000；100%的数据中，字符串长度不超过50000。

输出描述:

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