~4~	~9~	~2~
~3~	~5~	~7~
~8~	~1~	~6~

Jenny is obsessed with ~3 \times 3~ Magic Squares. In case you have forgotten, a ~3 \times 3~ Magic Square contains all integers from ~1~ to ~9~ arranged so that every row, column, and diagonal adds up to the same number. The earliest known Magic Square is the Lo Shu Square (shown at right) discovered in China more than 2600 years ago. There are only ~7~ other ~3 \times 3~ Magic Squares, all obtained by rotation and reflection of the original Lo Shu Square:

~8~	~1~	~6~
~3~	~5~	~7~
~4~	~9~	~2~

~6~	~1~	~8~
~7~	~5~	~3~
~2~	~9~	~4~

~4~	~3~	~8~
~9~	~5~	~1~
~2~	~7~	~6~

~2~	~7~	~6~
~9~	~5~	~1~
~4~	~3~	~8~

~2~	~9~	~4~
~7~	~5~	~3~
~6~	~1~	~8~

~6~	~7~	~2~
~1~	~5~	~9~
~8~	~3~	~4~

~8~	~3~	~4~
~1~	~5~	~9~
~6~	~7~	~2~

Jenny's friends have learned not to leave their Sudoku puzzles unattended when she's around. She will take any fully or partially completed Sudoku puzzle she finds and play a game of her own invention called "Lo Shudoku", in which she transforms the ~9 \times 9~ Sudoku board into a set of nine Magic Squares using a restricted set of moves. Then she writes down a "Lo Shudoku" square in the margin that shows the number of moves she used for each of the nine squares:

Original Sudoku Board

	~1~		~5~	~9~	~6~	~8~	~7~	~3~
~9~			~4~	~1~	~3~			~6~
		~5~	~8~	~7~	~2~	~4~	~1~	~9~
~1~	~7~	~2~		~4~			~9~
~8~	~6~	~3~	~2~	~5~	~9~
~5~	~4~	~9~		~6~			~3~	~8~
~7~	~2~	~6~	~9~	~8~	~4~	~3~	~5~	~1~
~3~			~1~					~4~
~4~	~9~	~1~	~6~	~3~	~5~	~7~	~8~	~2~

~\Huge\Longrightarrow~

Jenny's Transformation

~8~	~1~	~6~	~4~	~9~	~2~	~4~	~9~	~2~
~3~	~5~	~7~	~3~	~5~	~7~	~3~	~5~	~7~
~4~	~9~	~2~	~8~	~1~	~6~	~8~	~1~	~6~
~2~	~9~	~4~	~8~	~3~	~4~	~2~	~9~	~4~
~7~	~5~	~3~	~1~	~5~	~9~	~7~	~5~	~3~
~6~	~1~	~8~	~6~	~7~	~2~	~6~	~1~	~8~
~8~	~1~	~6~	~8~	~3~	~4~	~8~	~1~	~6~
~3~	~5~	~7~	~1~	~5~	~9~	~3~	~5~	~7~
~4~	~9~	~2~	~6~	~7~	~2~	~4~	~9~	~2~

Jenny's
"Lo Shudoku"
Square
~\Huge\Downarrow~

~8~	~5~	~6~
~5~	~7~	~7~
~4~	~6~	~7~

When she plays Lo Shudoku, Jenny works on each of the nine ~3 \times 3~ squares, turning them into Magic Squares one by one. When transforming a ~3 \times 3~ square, she always uses as few moves as possible, and she always proceeds in two separate phases:

1. First, she fills in all the blank spaces with the remaining integers from ~1~ to ~9~. Each number filled in counts as one move.
2. Once all the blanks are filled, she repeatedly swaps pairs of integers until she has a Magic Square. Each swap counts as one move.

When she has transformed each square in this way, she produces her Lo Shudoku square showing the number of moves she used to create each of the nine Magic Squares. In the example above, the Lo Shudoku square shows that the top left Magic Square took ~8~ moves, the ones to its right and beneath it took ~5~ moves each, and so on.

Here is one way that Jenny could transform top right ~3 \times 3~ square from the example above:

~8~	~7~	~3~
		~6~
~4~	~1~	~9~

~8~	~7~	~3~
	~5~	~6~
~4~	~1~	~9~

~8~	~7~	~3~
~2~	~5~	~6~
~4~	~1~	~9~

~8~	~9~	~3~
~2~	~5~	~6~
~4~	~1~	~7~

~8~	~9~	~3~
~2~	~5~	~7~
~4~	~1~	~6~

~4~	~9~	~3~
~2~	~5~	~7~
~8~	~1~	~6~

~4~	~9~	~2~
~3~	~5~	~7~
~8~	~1~	~6~

In phase one she fills in the ~5~ and ~2~ first, then in phase two she makes ~4~ swaps to complete the Magic Square. This is not the only way she could have made a Magic Square from the original numbers, but there is no shorter path to a Magic Square than this. She records this minimum number of moves ~(6)~ in the top right corner of her Lo Shudoku square.

The input contains ~5~ test cases. Each test case will consist of ~9~ lines of ~9~ digits, representing a Sudoku board. The Sudoku board might be completely filled in, or it might be partially filled in. If it is partially filled in, the blank spaces will be represented as zeros. Your program must output a Lo Shudoku square for each Sudoku board given. For ease of reading, each Lo Shudoku square should be followed by ---.

Sample Input

010596873
900413006
005872419
172040090
863259000
549060038
726984351
300100004
491635782
329847651
748561392
156392478
514726839
673985124
892413765
965138247
287654913
431279586
206004900
040900100
900800002
700045090
064389270
090120004
400003008
005008020
003500407
093006500
652830070
007500036
000060108
000908000
501040000
140002600
060097315
009600280
000050086
649300070
000640100
030021009
106000708
400980030
008072000
060003852
250060000

Sample Output

856
577
467
---
655
443
525
---
787
878
888
---
688
988
977
---
888
787
778
---

Educational Computing Organization of Ontario - statements, test data and other materials can be found at ecoocs.org