003 - ぱずる

ぱずる

もりたくんはすごくパズルが大好き。 そのパズルは9×9のマス目に１〜９の数字を配置するパズル。 このパズルでは以下の規則で数字を配置しなければならない。

---

同じ列に1つの数字はちょうど1回だけ現われる

同じ行に1 つの数字はちょうど1回だけ現われる

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

---

もりたくんは自分の作ったパズルの答え合わせをしてほしそうにしてます。 例えば、下の左図はその規則を満たした配置の一つです。 だけどもりたくんは下の右図のようによく規則に反した配置を作ってしまいます。 左端の列に「2」が2回現われて、「1」が1回も現われず、左から 2番目の列に「1」が2回現われて、 「2」が1回も現われていません。 規則に反している部分の数字の前には*(半角アスタリスク)を、誤っていない数字の前には空白を表示してください。

入力

複数のデータセットが与えられます。最初の行にデータセットの数 n が与えられます。各データセットの内容は以下のとおりです： パズルの状態を示す1行9文字、9行からなる数字列(整数;半角空白区切り)

出力

各データセットについて以下を出力してください。 与えられた数字と*(半角アスタリスク)と空白。誤っている数字の前には*(半角アスタリスク)、誤って いない数字の前には半角空白を付加する。 データセットの間に1行の空行を入れてください。

---

入出力例

入力例

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

出力例

*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