고등수학 수업

헨리는 National Search University of This and That의 지루한 고등수학 수업 시간에 졸고 있다. 그러다 선생님이 다음 문제를 풀라고 시키자 갑자기 깨어난다. 정수로 이루어진 $n \times n$ 행렬 $A$가 주어지면, 헨리는 다음 조건을 만족하는 가역 정수행렬 $L$과 $R$을 찾아야 한다.

• $B = LAR$은 대각행렬이다.
• $b_{i,i}=0$이 되는 것은 $i > j$인 경우에만 성립하도록 하는 $j$ ($0 \le j \le n$)가 존재한다.
• $2$ 이상 $j$ 이하의 모든 $i$에 대해 $b_{i,i}$는 $b_{i-1,i-1}$로 나누어떨어진다.

정수행렬 $C$가 가역이라는 것은 $CC^{-1}=I$를 만족하는 정수행렬 $C^{-1}$이 존재한다는 뜻이다. 여기서 $I$는 단위행렬이다.

헨리는 대부분의 수업을 졸면서 보내서 이 문제를 어떻게 푸는지 모른다. 그래서 당신에게 도움을 요청한다.

입력 파일에는 여러 개의 테스트 케이스가 들어 있다.

각 테스트 케이스는 행렬의 크기 $n$으로 시작하고, 이어서 각 줄에 정수 $n$개씩 $n$줄에 걸쳐 행렬이 주어진다. ($2 \le n \le 5$이고, 행렬의 모든 원소는 $-10$ 이상 $10$ 이하이다.)

입력은 $n = 0$인 줄로 끝난다. 입력 파일 하나에는 최대 100개의 테스트 케이스가 있다.

각 테스트 케이스마다 정수행렬 $L$, $L^{-1}$, $R$, $R^{-1}$ 네 개를 출력한다. 행렬 사이에는 빈 줄을 둔다. 해가 여러 개라면 그중 아무거나 하나를 출력하면 된다. 이러한 행렬은 항상 존재함이 보장되어 있다.