모두를 위한 정의

아르데니아가 전쟁에 나선다. 이 명망 높은 부대는 정확히 기사 $k$명과 말 $k$마리로 이루어져 있다. 이들 사이에는 상호 신뢰 관계가 정해져 있어, 기사 $i$가 말 $j$를 신뢰한다고 하면 대칭적으로 말 $j$도 기사 $i$를 신뢰한다. 한 마리의 말은 임의의 수의 기사를 신뢰할 수 있고, 한 명의 기사도 임의의 수의 말을 신뢰할 수 있다.

전투를 치르기 전마다 부대는 하나의 배정을 만든다. 각 기사에게는 그 기사가 신뢰하는 말 한 마리가 주어지며, 서로 다른 두 기사에게 같은 말을 줄 수는 없다. 즉, 배정이란 신뢰 관계를 지키면서 $k$명의 기사 전원과 $k$마리의 말 전원을 일대일로 짝짓는 방법이다.

서로 다른 두 전투는 서로 다른 배정을 사용해야 하며, 부대는 유효한 서로 다른 배정 하나마다 전투를 한 번씩 치른다. 신뢰 관계가 주어질 때, 부대가 준비된 전투의 수를 구하여라.

첫 번째 줄에 테스트 케이스의 수 $Z$ ($1 \le Z \le 100$)가 주어진다.

각 테스트 케이스의 첫 줄에는 기사의 수 $k$ ($1 \le k \le 20$)가 주어지며, 이는 말의 수와 같다. 이어지는 $k$개의 줄에는 각각 정확히 $k$개의 문자가 주어지고, 각 문자는 0 또는 1이다. $i$번째 줄의 $j$번째 문자가 1이면 기사 $i$가 말 $j$를 신뢰하는 것이고, 0이면 신뢰하지 않는 것이다.

각 테스트 케이스마다, 부대가 준비된 전투의 수, 즉 유효한 서로 다른 배정의 수를 한 줄에 하나의 정수로 출력한다. 이 값은 최대 $20!$이므로 항상 부호 있는 64비트 정수에 들어간다.