논문 발표

2M명의 과학자가 하루 동안 학회에서 논문을 발표할 예정이다. 하루는 오전 세션과 오후 세션 두 개로 나뉘며, 두 세션 사이에는 점심시간이 있다. M명은 오전 세션에서, 나머지 M명은 오후 세션에서 발표한다.

어떤 과학자는 자신의 논문보다 앞서 다른 과학자의 논문이 발표되어야 한다. 예를 들어 과학자 A가 "그래프 이론"을, 과학자 B가 "최대 유량-최소 절단"을 발표한다면 A가 B보다 먼저 발표해야 한다. 점심시간은 교류와 파티의 시간이라 참석자들이 앞 세션의 논문을 잊기 쉽다. 그래서 의존하는 과학자(이 예에서는 B)는 자신이 의존하는 과학자(이 예에서는 A)와 같은 세션에서 발표해야 한다. 주어진 의존 관계에서 가능한 발표 순서의 수를 구하라.

첫 줄에 테스트 케이스의 수를 나타내는 정수 $T$ ($T \le 20$)가 주어진다.

각 테스트 케이스는 정수 $M$ ($1 \le M \le 8$)으로 시작한다. 이어지는 $2M$개의 줄에는 각각 $2M$개의 문자가 주어지며, 문자는 'Y' 또는 'N'이다. i번째 줄의 j번째 문자가 'Y'이면 과학자 i가 과학자 j에게 의존한다는 뜻이고, 'N'이면 의존 관계가 없다는 뜻이다. 자기 자신에게 의존하는 과학자는 없다.

각 테스트 케이스마다 과학자들의 가능한 발표 순서의 수를 한 줄에 출력한다.