Su-Su-Sudoku

Time Limit: 1000ms
Memory Limit: 32768KB
This problem will be judged on HDU. Original ID: 2780
64-bit integer IO format: %I64d      Java class name: Main

Description

By now, everyone has played Sudoku: you're given a 9-by-9 grid of boxes which you are to fill in with the digits 1 through 9 so that 1) every row has all nine digits, 2) every column has all nine digits, and 3) all nine 3-by-3 subgrids have all nine digits. To start the game you are given a partially completed grid and are asked to fill in the remainder of the boxes. One such puzzle is shown below.



In this problem, you will be given Sudoku grids which you have nearly completed; indeed you've filled in every box except five. You are asked to complete the grid, or determine that it's impossible. (You might have already made an error!)

Input

The first line of input will contain a positive integer indicating the number of test cases to follow. Each test case will be a nearly completed Sudoku grid consisting of 9 lines, each containing 9 characters from the set of digits 0 through 9. There will be exactly five 0's in each test case, indicating the five unfilled boxes.

Output

Output for each test case should be either

Could not complete this grid.

if it is impossible to complete the grid according to the rules of the game, or the completed grid, in the form given below. (There are no blank spaces in the output.) If there is a way to complete the grid, it will be unique. Separate test cases with a blank line.

Sample Input

2 
481253697 
267948105 
539671204 
654389712 
908704563 
173562849 
702136958 
315897426 
896425371 
481253697 
267948105 
539671284 
654289710 
908704562 
173562849 
702136958 
315897426 
896425371

Sample Output

481253697 
267948135 
539671284 
654389712 
928714563 
173562849 
742136958 
315897426 
896425371 

Could not complete this grid.

Source

Language: 
Theme: 
Share Code? 

Powered by NB231 | Current Style: .