Paper Presentation

2M scientists are scheduled to present papers at a conference in one day. The day is divided into two slots, a morning slot and an evening slot, and a lunch break separates them. M scientists present in the morning slot and the remaining M present in the evening slot.

Some scientists depend on papers from other scientists being presented before theirs. For example, if scientist A presents "Graph Theory" and scientist B presents "Max flow-Min cut", then A must present before B. The lunch break is a time for socializing and partying, and attendees tend to forget the papers from the previous slot. For this reason, a dependent scientist (B in this example) must present in the same slot as the scientist they depend on (A in this example). Given the dependencies, find the number of possible orderings of the presentations.

The first line contains an integer $T$ ($T \le 20$), the number of test cases.

Each test case starts with an integer $M$ ($1 \le M \le 8$). The next $2M$ lines each contain $2M$ characters, either 'Y' or 'N'. If the $j$-th character of the $i$-th line is 'Y', then scientist $i$ depends on scientist $j$. If it is 'N', there is no dependence. No scientist depends on themselves.

For each test case, print one line containing the number of possible orderings of the scientists.