사라진 반마방진 나이트 투어

$n$행 $m$열 판의 나이트 투어는 각 칸에 $1$부터 $nm$까지의 정수를 하나씩 적은 것이고, 번호가 $k+1$인 칸은 번호가 $k$인 칸에서 나이트가 한 번에 이동하는 칸이다. 나이트는 가로로 두 칸과 세로로 한 칸, 또는 가로로 한 칸과 세로로 두 칸 이동한다. 아래 그림은 $8 \times 8$ 판의 나이트 투어다.

정사각형 판의 나이트 투어에서 모든 행의 합이 같고 모든 열의 합도 같으면 그 투어를 반마방진이라고 부른다. $8 \times 8$ 판에서 그 합은 $260$이다. $1 + 2 + \dots + 64 = 2080$이고 $2080 / 8 = 260$이기 때문이다.

아래 그림처럼 숫자 일부를 지운 $8 \times 8$ 반마방진 나이트 투어가 주어진다. 지운 숫자를 다시 채워서 판 전체를 반마방진 나이트 투어로 되돌리고, 남아 있는 숫자는 모두 원래 칸에 그대로 둔다.

채우는 방법이 여러 가지인 판도 있다. 그런 경우에는 사전순으로 가장 작은 판을 출력한다. 완성한 판의 숫자 64개를 위쪽 행부터 아래쪽 행까지, 각 행에서는 왼쪽부터 오른쪽으로 읽어 수열을 만들고, 그 수열을 사전순으로 비교한다.

첫 줄에 데이터 세트의 개수 $P$ ($1 \le P \le 20$)가 주어진다. 각 데이터 세트는 독립적으로 처리한다.

데이터 세트는 9줄이다. 첫 줄에는 데이터 세트 번호 $K$가 주어지며, 데이터 세트에는 나오는 순서대로 $1$번부터 $P$번까지 번호가 붙는다. 이어지는 8줄에는 각각 정수 8개가 공백으로 구분되어 주어지고, 판의 한 행을 위쪽 행부터 차례로 나타낸다. 값이 $-1$이면 그 칸의 숫자를 지웠다는 뜻이다. 나머지 값은 $1$ 이상 $64$ 이하의 정수이고, 한 데이터 세트에서 같은 숫자가 두 번 나오지 않는다.

각 데이터 세트에는 숫자 64개 중 적어도 20개가 남아 있고, 남아 있는 숫자와 일치하는 $8 \times 8$ 반마방진 나이트 투어가 적어도 하나 있다.

각 데이터 세트마다 9줄을 출력한다. 첫 줄에는 데이터 세트 번호 $K$를 출력한다. 이어지는 8줄에는 완성한 판의 한 행에 있는 숫자 8개를 위쪽 행부터 차례로, 공백 하나로 구분해 출력한다. 자리를 맞추는 여분의 공백은 넣지 않는다.

완성한 판은 반마방진 나이트 투어여야 하고, 입력에 주어진 숫자는 모두 같은 칸에 있어야 한다. 조건을 만족하는 판이 여러 개면 위에서 설명한 사전순으로 가장 작은 판을 출력한다.