SPOJ Brasil

Sudoku é uma tarefa muito simples. Um tabela quadrada com 9 linhas e 9 colunas é dividida em 9 quadrados menores de 3 x 3 como mostrado na figura. Em algumas das celulas estão escritos digitos de 1 a 9. As outras celulas são vazias. O objetivo é preencher as celulas vazias com digitos decimais de 1 a 9, um digito por celula, de tal modo que em cada linha, em cada coluna, e em cada subquadrado 3 x 3, todos os digitos de 1 a 9 apareçam. Escreva um programa que resolva um Sudoku.

Entrada

A entrada iniciará com o numero de casos de teste. Para cada caso de teste, 9 linhas se seguem, correspondendo às linhas da tabela. Em cada linha, uma string com exatamente 9 digitos decimais é dada, correspondendo às celulas nesta linha. Se uma celula está vazia, isto é representa por um '0'.

Saída

Para cada caso de teste, seu programa deve imprimir a solução no mesmo formato dos dados de entrada. As celulas vazias tem de ser preenchidas de acordo com as regras. Em caso de haver mais de uma solução, imprima qualquer uma. É garantido que todas entradas tem solução válida.

Exemplo

Entrada:
1
103000509
002109400
000704000
300502006
060000050
700803004
000401000
009205800
804000107

Saída:
143628579
572139468
986754231
391542786
468917352
725863914
237481695
619275843
854396127