좋은 행렬과 운이 좋은 행렬

정사각 이진 행렬은 행렬식이 홀수이면 좋은 행렬이라고 한다.

$n \times n$ 크기의 이진 행렬은 아래 탐욕 매칭 알고리즘이 크기 $n$의 매칭을 찾으면 운이 좋은 행렬이라고 한다. 알고리즘은 행렬을 위에서 아래로 한 줄씩 읽는다. 각 줄에서 이전에 한 번도 선택되지 않은 열에 1이 있으면, 그중 가장 왼쪽 열을 고른다.

$n \times n$ 크기의 좋은 행렬과 운이 좋은 행렬의 개수를 비교해야 한다. 이를 위해 작은 집합과, 큰 집합의 같은 크기 부분집합 사이의 전단사 함수를 만들어야 한다.

첫 줄에 테스트 케이스의 수 $t$가 주어진다. 이어서 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 줄에는 행렬의 종류를 나타내는 문자열 good 또는 lucky가 주어진다. 다음 줄에는 행렬의 크기 $n$ ($1 \leq n \leq 2000$)이 주어진다. 이어서 $n$개의 줄이 주어지며, $i$번째 줄은 길이가 정확히 $n$인 이진 문자열로 행렬의 $i$번째 행이다.

두 번째 실행에서 주어지는 행렬은 첫 번째 실행에서 프로그램이 출력한 행렬과 완전히 같으며, 같은 순서로 주어진다. 모든 테스트 케이스의 $n$의 합은 2000을 넘지 않는다.

실행할 때마다 $t$개의 답을 출력한다. 각 답은 한 줄에 정수 $-1$만 쓰거나, 입력 형식과 비슷하게 반대 종류의 행렬을 출력한다. 즉 한 줄에 $n$을 쓰고, 이어서 $n$개의 줄로 행을 출력한다.

대응은 전단사여야 한다. 첫 번째 실행에서 종류가 같은 행렬 $A$에 대한 답이 행렬 $B$였고, 두 번째 실행에서 $B$에 대한 답이 행렬 $C$였다면 $A = C$가 성립해야 한다. 각 $n$과 행렬 종류에 대해 $U$를 그 종류의 모든 $n \times n$ 행렬의 집합, $V$를 반대 종류의 모든 $n \times n$ 행렬의 집합이라 하자. $U$에 속한 서로 다른 행렬 중 $-1$로 답할 수 있는 것은 최대 $\max(|U| - |V|, 0)$개다.