Description

小W办了一个有关舞蹈的节目，并用NNEZ的公款作为奖金引来了许多位选手来参与。

对于任意两名选手，他们之间都有一名选手喜欢另一名选手。遗憾的是，这种喜欢总是单向的，也就是说如果选手$i$喜欢选手$j$，那么选手$j$就不会喜欢选手$i$。

现在小W要举办$T$期节目，第$i$期节目有$N_i$名选手报名，每期节目中需要有 3 名选手参与。在每期节目的最后，这些选手要一起表演轮舞，来凸显友谊第一，比赛第二的精神。为了让选手打消顾虑，小W要求在选出的选手中，每名选手都至少喜欢另外一名选手。

小W想知道，对于每期节目，有多少种选择选手的方式满足他的要求。然而他是第一次做这种工作，没有经验，所以他把任务交给了你。两种方案不同当且仅当有一位选手在一个方案中出现而在另一个方案中没有出现。

Format

Input

第一行输入一个整数$T$，表示小W要举办的期数。

接下来是$T$组输入，每组输入对应一期节目。

每组输入的第一行输入一个整数$N_i$，表示这期节目中选手的数量。

接下来$N_i$行，每行输入一个长为$N_i$的字符串，其中第$i$行的第$j$个字符如果为$Y$，表示第$i$位选手喜欢第$j$位选手，否则如果为$N$，则相反。保证第$i$行第$j$个字符和第$j$行第$i$个字符不同。第$i$行的第$i$个字符没有意义，你应该忽略。

Output

输出$T$行，每行输出一个整数，第$i$行应该输出第$i$期节目选择的方案数。

Samples

2
4
NYNY
NNYY
YNNN
NNYN
4
YYNY
NYYY
YNYN
NNYY

2
2

Limitation

【提示】

请注意多组数据带来的影响。每组数据处理完后，可能用到的计数器需要清零。

若你不会读入字符串并处理，可参考下方

#include <cstdio>
#include <iostream>
#include <algorithm>
const int N = 2000 + 5;
using namespace std;
char s[N][N];
int g[N][N];
int main()
{
     int T;
    scanf("%d", &T);
    while (T--)
    {
        int n;
        scanf("%d", &n);
        for (int i = 1; i <= n; i++)
            scanf("%s", s[i] + 1);
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
            {
                if (s[i][j] == 'Y') g[i][j] = 1;
                else g[i][j] = 0;
            }

        /*
            此时已考虑了T组输入，将读入的字符串转为0 / 1数组。
           g[i][j] = 0 / 1表示i是否喜欢j
        */

        int ans = 0;
    }
    return 0;

}

【样例说明】

对于第一组数据：合法的选择方案有：$\{1,2,3\},\{1,3,4\}$。

【数据范围】

对于前$30\%$的数据：$T=1,3\le N_i\le 200$。

对于前$50\%$的数据：$1\le T\le 10,3\le N_i\le 200$。

对于后$50\%$的数据：$1\le T\le 3,3\le N_i\le 2000$。