/**************************
 *
 *	Stephen Fulwider
 *	BHCSI - 2007
 *	Sudoku Solver
 *
 **************************/

import java.io.*;
import java.util.*;

public class Sudoku
{
	int[] board;
	
	public static final int SIZE = 9;
	public static final int GRID_SIZE = (int)Math.sqrt(SIZE);
	public static Scanner fIn;
	
	/* init board */
	private Sudoku() throws IOException
	{
		board = new int[SIZE*SIZE];
		for (int i=0; i<SIZE*SIZE; i++)
			board[i] = fIn.nextInt();
	}
	
	/* solve puzzle using backtracking */
	private boolean solve()
	{				
		/* base case -- if solved, return true */
		if (solved())
			return true;
		
		int[] opens = getOpens();
		int[][] poss = new int[opens.length][];
		for (int i=0; i<opens.length; i++)
			poss[i] = getPossibles(opens[i]);
		
		/* get index of array with least possibilities */
		int leastPoss = SIZE+1;
		int leastIndex = -1;
		for (int i=0; i<poss.length; i++)
			if (poss[i].length < leastPoss)
			{
				leastPoss = poss[i].length;
				leastIndex = i;				
			}
		
		/* try each possibility -- if it doesn't work, backtrack */
		for (int i=0; i<poss[leastIndex].length; i++)
		{
			board[opens[leastIndex]] = poss[leastIndex][i];
			if (solve())
				return true;
			board[opens[leastIndex]] = 0;
		}
		return false;
	}
	
	private boolean solved()
	{
		/* if any 0's in puzzle, not solved yet */
		for (int i=0; i<SIZE*SIZE; i++)
			if (board[i] == 0)
				return false;
				
		/* otherwise, only trying valid places, so solved */
		return true;
	}
	
	/* get list of all spots on board that are open */
	private int[] getOpens()
	{
		ArrayList<Integer> opens = new ArrayList<Integer>();
		for (int i=0; i<SIZE*SIZE; i++)
			if (board[i] == 0)
				opens.add(i);
				
		int[] opens2 = new int[opens.size()];
		for (int i=0; i<opens2.length; i++)
			opens2[i] = opens.get(i);
		return opens2;
	}
	
	/* get all possible values a square at a given index can be */
	private int[] getPossibles(int index)
	{
		boolean[] nums = new boolean[SIZE];
		Arrays.fill(nums,true);
		
		/* remove row numbers */
		int rowStart = index - (index%SIZE);
		for (int i=rowStart; i<rowStart+SIZE; i++)
			if (board[i] != 0)
				nums[board[i]-1] = false;
		
		/* remove col numbers */	
		int colStart = index-rowStart;
		for (int i=colStart; i<colStart+(SIZE*SIZE); i+=SIZE)
			if (board[i] != 0)
				nums[board[i]-1] = false;
				
		/* remove grid numbers */
		rowStart /= SIZE;
		int gridStart = ((rowStart-(rowStart%GRID_SIZE))*SIZE) + (colStart-(colStart%GRID_SIZE));
		for (int i=gridStart; i<gridStart+(SIZE*(GRID_SIZE-1))+GRID_SIZE; i++)
		{
			if (board[i] != 0)
				nums[board[i]-1] = false;
			if (i%(SIZE/GRID_SIZE) == GRID_SIZE-1)
				i += (SIZE-GRID_SIZE);
		}
		
		/* find which numbers are valid, put in int array, return */
		int cnt=0;
		for (int i=0; i<SIZE; i++)
			if (nums[i])
				cnt++;
		int[] poss = new int[cnt];
		cnt = 0;
		for (int i=0; i<SIZE; i++)
			if (nums[i])
				poss[cnt++] = i+1;
		return poss;
	}
	
	/* print board */
	private void printBoard()
	{
		for (int i=0; i<SIZE*SIZE; i++)
		{
			if (i != 0 && i%SIZE == 0)
			{
				System.out.println();
				if (i%(SIZE*GRID_SIZE) == 0)
				{
					for (int j=0; j<SIZE*(SIZE<10?2:3)+GRID_SIZE+(SIZE<10?0:1); j++)
						System.out.print("-");
					System.out.println();
				}
			}
			if (i%GRID_SIZE == 0 && i%SIZE != 0)
				System.out.print("| ");
			
			System.out.print((SIZE>10 && board[i] < 10 ? " " : "") + board[i] + " ");
			
		}
	}
	
	/* main to get it all going */
	public static void main(String[] args) throws IOException
	{
		Scanner stdIn = new Scanner(System.in);
		
		String fileIn = "";
		if (args.length == 1)
			fileIn = args[0];
		else
		{
			System.out.print("Input file> ");
			fileIn = stdIn.next();
		}
		fIn = new Scanner(new File(fileIn));
		int n = fIn.nextInt();
		
		/* try to solve each puzzle */
		for (int i=1; i<=n; i++)
		{
			Sudoku game = new Sudoku();
			System.out.println("Test case " + i + ":\n");
			if (game.solve())
				game.printBoard();
			else
				System.out.print("No solution possible.");
			System.out.println("\n\n");
		}
	}
}