Problem 21682 --Sudoku Solver

21682: Sudoku Solver

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 3  Solved: 2
[Submit][Status][Web Board][Creator:][下载FPS1元][添加到购物车][下载测试数据1元][36kb]

Description

Sudoku is a logic-based, combinatorial, number-placement puzzle. The objective is to fill a 9×9 grid with digits so that each column, each row, and each of the nine 3×3 sub-grids that compose the grid (also called "boxes", "blocks", "regions", or "sub-squares") contains all of the digits from 1 to 9. The puzzle setter provides a partially completed grid, which typically has a unique solution. Or we can say, the same single integer may not appear twice in the same 9×9 playing board row or column or in any of the nine 3×3 sub-regions of the 9×9 playing board. Now you are given a partially filled Sudoku board that has a unique(唯一) solution. Your task is to fill the board.

Given Sudoku Puzzle

Puzzle with Solution

Input

Input starts with an integer T (≤ 30), denoting the number of test cases.

Each case starts with a blank line. Then there will be 9 lines, each containing 9 characters denoting the board as described. Empty places will be marked by a '.'.

Output

For each case, print the case number in a single line. Then print the solution in 9 lines with 9 characters in each line.

Sample Input

1
.46...9..
.3.1.....
.2..6..85
...87....
6...3...4
....14...
79..5..3.
.....2.4.
..2...61.

Sample Output

Case 1:
146528973
835197462
927463185
459876321
618235794
273914856
794651238
361782549
582349617

HINT

Source

[Submit][Status]