스도쿠

스도쿠는 아홉 개의 $3 \times 3$ 칸으로 나뉜 $9 \times 9$ 격자에서 하는 게임이다. 각 가로줄, 각 세로줄, 그리고 각 $3 \times 3$ 칸에 $1$부터 $9$까지의 숫자가 정확히 한 번씩 들어가도록 격자를 모두 채워야 한다.

스도쿠 문제는 $9 \times 9$ 격자로 주어지며, 숫자가 채워진 칸은 그 숫자로, 빈 칸은 $0$으로 표시된다. 이러한 문제가 주어졌을 때 스도쿠를 푸는 프로그램을 작성하시오.

첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 스도쿠 격자를 나타내는 $9$개의 줄로 이루어지며, 각 줄은 $0$부터 $9$까지의 숫자 $9$개로 된 문자열이다. 여기서 $0$은 빈 칸을 뜻한다. 각 테스트 케이스에는 항상 정확히 다섯 개의 $0$이 주어진다.

규칙을 어기지 않고서는 격자를 완성할 수 없는 경우에는

Could not complete this grid.

를 출력한다.

풀 수 있는 경우에는 입력과 같은 형식으로 완성된 격자를 $9$개의 줄에 걸쳐 출력한다. 연속한 테스트 케이스 사이에는 빈 줄을 출력한다. 풀 수 있는 경우, 입력은 항상 정답이 유일하도록 주어진다.