パズル

たろう君は 9 × 9 のマス目に 1〜9 の数字を配置するパズルで遊んでいます。このパズルでは以下の規則で数字を配置しなければいけません。

• 同じ列に 1 つの数字はちょうど 1 回だけ現われる
• 同じ行に 1 つの数字はちょうど 1 回だけ現われる
• 二重線で区切られた 3 × 3 の各範囲には、1 つの数字はちょうど 1 回だけ現われる

例えば、下の図 1 はそのような規則を満たした配置の一つです。しかしたろう君は、図 2 のようによく規則に反した配置を作ってしまいます。左端の列に「2」が 2 回現われて、「1」が 1 回も現われず、左から2 番目の列に「1」が 2 回現われて、「2」が 1 回も現われていません。

図 1	図 2

たろう君を助けるために、数字の配置を読み込んで、その配置が規則を満たしているかどうかを調べ、規則に反していたらその場所を出力するプログラムを作成してください。3 つの規則に照らして誤っている (2 回以上現れている) 数字の前には * (半角アスタリスク)を、誤っていない数字の前には空白を表示してください。

Input

複数のデータセットが与えられます。最初の行にデータセットの数 n (n ≤ 20) が与えられます。各データセットとして、パズルの状態を示す 1 行 9 文字、9 行からなる数字列が与えられます。

Output

各データセットについて以下を出力してください。

与えられた数字と * (半角アスタリスク)と空白。誤っている数字の前には *、誤っていない数字の前には半角空白を付加する。

データセットの間に 1 行の空行を入れてください。

Sample Input

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

Output for the Sample Input

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

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

---