Програмчлалын олимпиадын бодлогын архив

Судоку-г дараах дүрмээр 9x9 хөлөг дээр нүд бүрт 1-9 хүртлэх тооны аль нэгийг бичиж тоглоно:
1. Мөр, багана бүр 1-9 хүртлэх тоог бүгдийг агуулна
2. 3х3 хэмжээтэй 9-н ширхэг дэд хэсэг бүр 1-9 хүртлэх тоог бүгдийг агуулна.
Жишээг доорх зурагт үзүүлэв:

Энэ бодлого дээр танд 5-н нүднээс бусдыг нь бөглөсөн судокугийн хөлөг өгөгдөнө. Энэ тоголтыг дуусгах, эсвэл дуусгах боломжгүй (алдаа гарсан байж болно) гэдгийг тодорхойлох хэрэгтэй.

Input

Эхний мөрөнд тестийн тоо байрлана. Тест бүр нь 9 мөрөөс тогтох ба мөр бүрт 0-9 тоонуудаас байрлана. Бөглөгдөөгүй байгаа 5 нүдийг илэрхийлэх яг 5 ширхэг 0 байгаа. Мөрүүдийн эхэнд нэг хоосон зай байж болно.

Output

Хэрэв тоглолтыг дуусгах боломжгүй бол "IMPOSSIBLE." гэсэн үгийг хэвлэх ба боломжтой бол бөглөгдсөн судокуг оролтонд өгсөн байдлаар хэвлэнэ (тоонуудын хооронд нэг хоосон зай хэвлэнэ). Хэрэв тоглолтыг дуусгах боломжтой бол энэ нь ганц байхаар өгөгдөнө. Тестийн гаралтуудыг хоосон мөрөөр тусгаарлана.

Example

Input:
2
4 8 1 2 5 3 6 9 7
2 6 7 9 4 8 1 0 5
5 3 9 6 7 1 2 0 4 
6 5 4 3 8 9 7 1 2 
9 0 8 7 0 4 5 6 3
1 7 3 5 6 2 8 4 9
7 0 2 1 3 6 9 5 8
3 1 5 8 9 7 4 2 6
8 9 6 4 2 5 3 7 1
4 8 1 2 5 3 6 9 7
2 6 7 9 4 8 1 0 5
5 3 9 6 7 1 2 8 4
6 5 4 2 8 9 7 1 0
9 0 8 7 0 4 5 6 2
1 7 3 5 6 2 8 4 9
7 0 2 1 3 6 9 5 8
3 1 5 8 9 7 4 2 6
8 9 6 4 2 5 3 7 1

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

IMPOSSIBLE.