P19480 [HackerEarth] You are working in the HR department of a huge corporation. Each employee may have several direct managers and/or several direct subordinates. Of course, his subordinates may also have t
普及
题目描述

You are working in the HR department of a huge corporation. Each employee may have several direct managers and/or several direct subordinates. Of course, his subordinates may also have their own subordinates, and his direct managers may have their own managers. We say employee X is a boss of employee Y if there exists a sequence of employees A, B, ..., D, such that X is the manager of A, A is the manager of B, and so on, and D is the manager of Y (of course, if X is a direct manager of employee Y, X will be a boss of employee Y). If A is a boss of B, then B can not be a boss of A. According to the new company policy, the salary of an employee with no subordinates is 1. If an employee has any subordinates, then his salary is equal to the sum of the salaries of his direct subordinates.

You will be given a String[] relations, where the j-th character of the i-th element is 'Y' if employee i is a direct manager of employee j, and 'N' otherwise. Find the sum of the salaries of all the employees.

Input:
The first line of the input contains an integer T (1 ≤ T ≤ 10), the number of test cases. The T test cases follow. Each test case contains an integer n (1 ≤ n ≤ 40), followed by n lines, each containing a string of length n.
Output:
For each test case, output consists of single line with the required answer - sum of the salaries of all the employees.

SAMPLE INPUT
1
4
NNYN
NNYN
NNNN
NYYN

SAMPLE OUTPUT
5

输入格式

见题面

输出格式

见题面

样例输入
9 15 NNYYNYYYYNNNYYN NNYNNNNNNNNNNNN NNNNNNNNNNNNNNN NYYNNYNYNNYNNYN NNNYNYNYYNYNYYN NNYNNNNYNNNNNNN NYYNYYNYYYYYYNN NNNNNNNNNNNNNNN NYNYNYNNNNYYNNY NYYYNNNYNNNNYYN NNYNNYNNNNNYNNN NNYNNNNYNNNNNNN NNYYNNNYNNNYNYN NYNNNNNYNNNYNNN NYYYNNNYNNYNYYN 17 NNNNNYNNNNNNNYNYN NNYNNYNNNNNNYNNNN NNNNNNNNNNNNNNYNN NNNNNYNYNNNNNNYNN NNNNNNNYNYYNYNYNN NNYNNNNNNYNNNNYNN NYNNNNNYNNNNYYNNN NNNNNNNNNYYNNNNNN YYNYNNNYNYNNYNYNN NNNNNNNNNNNNNNNNN NNNNNNNNNNNNNNNNN YYNNYNNNYYYNNYYNN NNYNNNNNNYYNNNYNN NNYNNNNNNYYNNNYYN NNNNNNNNNNNNNNNNN NNNNNNNNNNNNNNNNN NNNYYYYYNYYNYYNYN 22 NYYYNYYNNYNYYNYYNYNNYY NNNNNNNNNNYNYYNNYYNYNN NNNNNNNYYNYNYNNYNNNNNN NNYNNNNNNNYYYNNYNNNYNY NNNNNNYYNNYNNYNNYNYNYY NYYNNNNNYNYNNNNYNNNNNY NYNNNYNYYNNNYNNYYYNNNY NNNNNNNNNNNNNNNNNNNNNN NNNNNNNYNNNNNNNYNNNNNN NNYNNNNYYNNNYYNYYNNYYY NNNNNNNYNNNNYNNYNNNNNN NNYNNNNYYNNNNNNNNNNYNN NNNNNNNYNNNNNNNNNNNNNN NNNNNNNYYNYNNNNYNNNNNN NYNNNNNYNNYNYYNYYYNNNN NNNNNNNYNNNNNNNNNNNNNN NNNNNNNNYNYNYYNNNNNNNY NNNNNNNYYNYNYNNNNNNYNY NNYYNNYNYNNYYYNNNYNNNY NNYNNNNNYNNNYNNNNNNNNN NYYNNYNYYNYNNNNNNNYYNN NNNNNNNYYNYNNNNYNNNNNN 24 NNYNNYYNYYNNNNNNNYNYYNYN NNNNNNNNNNYNNNNNNYNNNNYN NYNNNNNNNNYNYNNNNNNNNNNN NYYNNYNNYNYNNNNNNNNNNNNN YYNNNNYNNNYYYYNYYYYNYYNN NNYNNNNNYNYNYNNNNYNNNNYY NYNYNNNYNYNYYNNNYYNYYNNN NYNYNNNNYNYNNNNNYNNNNNYN NYNNNNNNNNYNNNNNNNNNNNNN NNYYNYNNNNNNYNNNNNNNYNNY NNNNNNNNNNNNNNNNNYNNNNYN NNYNNNNNYYYNNNNNNNNNYNNY NNNNNNNNNNNNNNNNNNNNNNYN NNYNNYYNYNNNYNYYYYYNNYYY NNNYNNNYYNYNYNNNYNYYYNYY NYNNNNNYYNNNNNNNYNYNNNYN NYYNNYNNNNYYNNNNNYNNYNNY NNNNNNNNNNNNNNNNNNNNNNNN NNNYNNNYYNNNNNNNNYNNNYNN NNNYNNNNNNNYYNNNNNNNYNYN NYYYNYNNYNNNYNNNNYNNNNNY NNNYNYNYNYYNNNNNNNNYNNYY NNNNNNNNNNNNNNNNNNNNNNNN NYNNNNNNNNYNNNNNNYNNNNNN 29 NNYNNNNNYYNNNNYYNNNNNNYNNNNNN NNYNYNNNNYNNYNNNNNNNYNNNNNNNN NNNNYNNNNNNNNNNNNNNNYNYNNNNNN YNYNYYYYYNYNYNNYNNNYYYNNYNNNY NNNNNNNNNNNNNNNNNNNNNNNNNNNNN YNYNNNYNNNNNNNYYNYNNNNYYNNYNN NNYNYNNNNNNNNNNYNNNNYNYNNNNNN NNNNNNYNNYNNYNYNNNNNNNNYYYYNN NNNNNNNNNNNNNNNNNNNNYNNNNNNNN NNNNNNNNNNNNNNNNNNNNNNNNNNNNN NYNNYYYNYYNYYNNYNNNNYYYNNYNNY YYYNNNYNNNNNYNYYNNNNNNYYYYYNN NNYNYNNNNYNNNNNYNNNNYNYNNNNNN YYNNNYYYYNYNNNNYNNYYNNNYYYYNN NNNNNNNNNNNNNNNNNNNNYNNNNNNNN NNNNYNNNNNNNNNYNNNNNYNNNNNNNN YNNNYNNNYYYNNYYYNYYYNNYNNNNNN NYNNNNYNNYNNYNNNNNNNYNNNNNNNN YYYNYNNNYYNYYNNNNYNNYNYYNYYYY NYNNNYYYYYYYYNYNNYNNYNNYNYYNN NNNNNNNNNNNNNNNNNNNNNNNNNNNNN YNYNYYNYYNNYYNNNNNNNYNYNNNYYN NNNNYNNNYNNNNNYNNNNNYNNNNNNNN NNYNYNNNYYNNYNNYNNNNYNNNNNNNN YYYNYYNNNNNNNNYNNNNNYNNYNYYNN YYYNYYYNYNNNYNNNNNNNNNYYNNYYN YYYNYNNNNNNNYNYYNNNNNNNNNNNNN YNNNYYNNNNNNNNNNNNNNNNNYNNNNN NYYNNNNNYYNNNNYYNYNNYNYYNNYYN 34 NNNNNYNNNYNNNNNNNNNNNNNNNNNNNNNNNN NNYYNNNNNNNNYNNYYYNNYYNNYNYNNNNNYN NNNNNYNNNNNYNNNYNNYNYNNYYNNNNNNYNY YNNNNYNYNYNYNNNNNYNNNNYYNNNNNNNNNY NNNNNYNNNNNNYNNNYYYNYNNNNYNYNNNYYY NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN YNYYNNNNNYNYNYNNYNYNNNNNYNNNNNNNYY NNNNNYNNNNNNNNNNNNNNNNNNNNNNNNNNNN NYYYYNNYNYNYYNNNYYYNYYYYYYYNNNNYNN NNNNNNNYNNNYNNNNNNNNNNNNNNNNNNNYNN NNNYNNNYNYNYNYNYYYNNYYYYNYYYNNNNNN NNNNNYNYNNNNNNNNNNNNNNNNNNNNNNNNNN YNNNNYNYNNNNNYNNYYYNYNYNNNNYNNNNYN NNNYNYNNNYNNNNNYNYYNYNYNNNNNNNNNNN YYYYYYYNNYYYNNNNYNNNYNYNNYNYNNNNNN NNNNNYNYNNNYNNNNNNNNNNNNNNNNNNNNNN NNNYNYNYNNNNNYNNNYYNYNNNNNNNNNNNYN NNNNNYNYNYNYNNNYNNNNNNYNYNNNNNNNNN NNNYNYNYNNNNNNNNNNNNYNYYNNNNNNNYNN NYNNYNNNNNNYYNYYYYNNNYNNYNYNNYNNNN NNNNNNNYNYNYNNNNNNNNNNNNNNNNNNNNNY NNYNYNYYNNNNYNNNNYYNYNYYNYNYNNNYNY YNNNNYNNNYNNNNNYNNNNNNNNYNNNNNNNNY NNNNNNNYNNNYNNNNNNNNYNNNNNNNNNNYNN NNNNNYNYNNNNNNNYNNNNYNNNNNNNNNNYNY NNYNNNNYNNNNNNNNNNYNYNYNNNNNNNNYYY NNYNNYYNNYNNNNNNYYYNNNYNNNNNNNNYNN NNYYNYNYNYNYNYNNNYNNNNYYYNNNNNNYNY NYYNNNYNNYNNYYYYYYYYNYYNNYNYNNYNYN NNNNNYYNNNNYYNNNNNNNYYNNYNYNNNNYNY YYNNYNYNNNNNNNYNNNYNYNYNYYYYNNNYYN NNNNNNNYNNNNNNNNNNNNNNNNNNNNNNNNNN YNYYNNNNNNNNNYNYNYYNNNNYYNNNNNNNNN NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN 39 NNNNNNNNNNNNYNNNYNNNNNNNYNNNNNNNNNNNYYN NNNNNNNNNNNNYNNYYNNNNNNNNNYNYNNNNNNNNNN YYNNNNNNNYNYYNNNYYYNNNYNNNNYNNNNNNNNYYN YNNNNNNNNNNNYNNYNYYYNNYNYNYNYNYYNYNNNYN NYNNNNNNNYNYNNNYYNNYNNNNYNNNYNNNNNYNYYN NYNNNNYNYYYYNYYYNYYNNNYNNNNNYNNYNNYNNYY NYYYYNNNYNNYNYYNYYNYYYNNYNYYYNYNYYYNNNY NNNNNNNNNYNYYNNNNNNNNNYNYNNNYNYNNNNNYNN NNNNYNNYNNNNNNYNYNYNYNYNNNYNNNYNYYYNNNY NNNNNNNNNNNNNNNNNNYNNNNNYNNNNNNNNNNNNNN NNYNNNNNNYNNNNNYYYYNNNYNNNYYNNYNNYYNYNN NNNNNNNNNNNNNNNNNNYNNNNNYNNNNNNNNNNNNNN NNNNNNNNNYNYNNNYYNNNNNNNYNNNYNNNNNNNNYN NNNNYNNNNNYNNNYNYYYYNNYNNNNNNNYNNYNNNNN YNNNNNNYNYYNNNNYYYYYNNYNNNYNNNYNYYNNNNN NNNNNNNNNYNNNNNNNNYNNNNNYNNNNNNNNNNNNYN NNNNNNNNNYNYNNNNNNNNNNNNNNYNNNNNNNNNNNN YNNNNNNNNNNYNNNNYNNYNNNNYNNNYNNNNNYNNNN NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN NNYNYNNNNNYNYYNNYNYYNNNNNNNNYNNNNYYNYNN NYNYYNNNNNYYYYNNYNYYNNYNYNNYYNYYNNYNYNN NNNNNNNNNNNYNNNNNNNNNNNNYNYNNNNNNNNNNYN YNYYYYNNNNNYYNNNNYNNYNYNYYNNNNYYYNNNYYN NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNYN YNYYYNYYYNNYYNYNYNYNNYYNNNNYNNYNNYNNYYY NNNNNNNNNNNYNNNNNNNNNNNNNNNNNNNNNNNNNYN YNNNNNNNNYNNNNNYNNNNNNYNYNYNYNNNNNNNNNN NNNNNNNNNYNNNNNYNNYNNNYNNNYNNNNNNNYNNYN NYYNYNNNNYYNYNYNYYNYNYYNNNYNYNNYNNNNYNN YYYNNNNNNYNNNNNYNYYNNNNNYNYNNNNNNNNNYNN NYNNYNNNNYNNYNNYYNYYNNNNNNNNNNNNNNYNYYN NNYNNNNNNYNNNNNNYYYNNNYNNNNNNNNNNNNNNNY NNNNNNNNNNNYNNNNNYYNNNNNYNYYNNNNNNNNYYN NNNNNNNNNNNNNNNYYNYNNNNNNNYNNNNNNNNNNYN YYNYNYYNYNNNNYNNYYYNYNYNYNNNYYNYYNNNYNY NYNNNNNNNNNNNNNNNNYYNNYNYNNNYNNNNNYNNNN NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN YYNNYNNNNYNNYNNYNYNNNNNNYNNYNNNNNNNNNNN 26 NNNNNYNNNNNYYNYNYYNNYYNNNN NNNNYNYNNYNYNYNNYNNNNNNYYN YYNNYNNYNYNNNYYYYNNNYNNYNY NNNNNNYNNNNYNNNNNNNNNYNNNN NNNNNNYNNNNNNNNNNNNNNYNNNN NYNYNNYNYYNYNNYYYYNYNYNYYY NNNNNNNNNNNYNNNNNNNNNNNNNN NYNNYNYNNNNYNYNNNYYNNNYNYY NYNYYNYNNNNYNYNNNNNNNYNYNN NNNYYNNNNNNYNNNNNNNNNNNYNY NNNYNYNNYNNYNNNYNYYYYNYYYN NNNNNNNNNNNNNNNNNNNNNNNNNN NNNYYNYYNNNNNNNNYYNYYNNNNN NNNYNNYNNNNYNNNNNNNNNNNNNY NNNYYNNNNNNNNYNNYYNNYYNYNY NNNNNNNYNNNYNYNNYYNNNYYYNN NNNNNNYNNNNNNNNNNNNNNYNYNY NYNYYNNNNYNYNNNNYNYNNNNNNY NNNNNNNNNNNNNYNNNNNNNNNYYN NNNYYNYYNYNNNYNNYYNNNNYNYY NYNNYNYNYNNNNYNYYYYNNNNNYN NNNNNNNNNNNYNNNNNNNNNNNNNN NNNYNNNNNNNYNYNNYNNNNNNYYY NNNNNNNNNNNNNNNNNNNNNNNNNN NNNNNNYNNYNYNNNNYNNNNNNYNY NNNYYNYNNNNYNNNNNNNNNYNNNN 25 NYNYNNYNNYNYNNNNNNYNYNYYY NNNNNNNNNNNNNNNNNNNNYNNNN NNNNNNYNNNNNNNNNYYNNNNNYN NNYNNNYNNNNNNNNNYYNNNNNYN NNYYNNNNNNYYNYYYNNNNYNNNN NYYYNNNYYNYNYYYNNNNYNYNNN NNNNNNNNNNNNNNNNNNNNYNNNN YYNYNNNNNNNYYNYNYYNYNNNNY NNYNYNNNNYNNYNYNYNYYYNNNY NNNNYNNNNNNYNYNYYYYNYNYYN NNYYNNYNNNNNNNNYYYNNYNNNN NNYYNNYNNNNNNYYYNYYNNNNNN NNYYYNYNNNNNNYNYYYYNYNNNN NNNNNNNNNNNNNNNNNYNNYNNYN NNYYNNYNNNNNNNNNYNYNNNNNN NYNNNNYNNNNNNNNNNYNNNNNYN NYNNNNNNNNNNNNNNNNNNYNNYN NYNNNNYNNNNNNNNNNNNNNNNNN NNNYNNNNNNNNNNNNYYNNYNNNN NNYNNNNNNNNNYNYNYYYNYNYNN NNNNNNNNNNNNNNNNNNNNNNNNN NNNYNNNNNYYNNNNNYNNYYNNYY NYYNNNNNNNNNNNYNYYNNNNNNN NNNNNNNNNNNNNNNNNNNNYNNNN NYYNNNNNNNNNNNNNNYYNYNYYN
样例输出
989 217 4887 49442 133307 1110974 2037927 38627 11058