Tudoku

Tom is a master of several mathematical disciplines. He recently founded a research lab at the university and teaches newcomers like Jim. In his first lesson he explained the game of Tudoku to Jim. Tudoku is a straightforward variant of Sudoku that starts from a board where almost every cell is already filled in — exactly the kind of board Tom leaves behind when he gives up on an ordinary Sudoku because he is too lazy to fill in the last few obvious cells. Help Jim solve every Tudoku that Tom leaves for him.

Sudoku is played on a 9 × 9 board divided into nine 3 × 3 blocks. Initially only a few cells contain numbers, and the goal is to fill the remaining cells so that every row, every column, and every 3 × 3 block contains each number from 1 to 9 exactly once.

Every Tudoku board can be solved by repeatedly applying the following rule: if some row, column, or 3 × 3 block already contains exactly eight numbers, the single empty cell in it is uniquely determined, so fill it in. Applying this rule repeatedly is guaranteed to complete every board in the input.

The first line contains the number of scenarios. Each scenario consists of nine lines of nine digits each. A digit of 0 marks a cell that Tom has not filled in and that you must fill. Each scenario is followed by an empty line.

For each scenario, first print a line of the form Scenario #i:, where i is the scenario number starting at 1. Then print the completed Tudoku board in the same format as the input, with every 0 replaced by the correct digit, as nine lines. Terminate the output for each scenario with a blank line.