Головоломки SuDoku

Эта простая игра без особой графики и каких-либо хитростей покоряет страну за страной. Изначально прославившись в Японии в 1986 году, сегодня “Sudoku” завоевала США, Австралию, Германию, Скандинавию, а также охватила и всю Великобританию, где кроссворды Sudoku входят в Топ-десятку самых продаваемых изданий.

В судоку играют на квадратном поле 9 на 9 клеток. Само поле поделено на районы (квадраты 3 на 3)

В начале игры известно некоторое число цифр в определенных клетках

Цель судоку заполнить все пустые клетки с помощью цифр 1-9 (по одной цифре на клетку), по следующим правилам:

1. Цифра может появиться только один раз в каждой строчке

Можно
Нельзя

2. Цифра может появиться только один раз в каждом столбце

Можно	Нельзя

3. Цифра может появиться только один раз в каждом районе

Можно	Нельзя

Проще говоря, одна и та же цифра может появиться только один раз в каждой строчке, столбце и районе.

В отличии от журналов и газет, в цифровом виде головоломку обычно описывают в виде строки состоящей из 81 символа. То есть все строчки головоломки записаны подряд одна за другой. Для записи используются символы ASCII '1' - '9' - для обозначения цифр и '.' - для обозначения пустого места. Например головоломка на рисунке выше может быть записана следующим образом:

В данной задаче Вам прийдется автоматизировать процесс решения таких головоломок и чем эффективнее и быстрее будет работать Ваша программа, тем больше очков вы получите. Очки в данной задаче зависят, как от количества решенных головоломок, так и от скорости работы программы. Большинство головоломок имеет единственное решение, но не все. В тестах присутствует несколько головоломок с несколькими возможными решениями. В данном случае правильным будет любое решение не противоречащее первоначально заданной головоломке. Вы можете быть уверены в том, что все поданные на вход SuDoku являются корректными.

Входные данные

t – число тестов, затем следуют t тестов. [t <= 500]
Каждый тест состоит из одной строчки длиной 81 символ, описывающей одну из головоломок SuDoku.

Выходные данные

Для каждого теста необходимо вывести на отдельной строчке букву Y если вы хотите решать этот тест или же N в противном случае. Далее в том случае если вы ответили Y, необходимо вывести строчку длиной 81, соответствующую корректно решенной головоломке.

Начисление очков

Количество очков полученное за данную задачу вычисляется по формуле: score = 200*total_solved/(200+time), где total_solved - число правильно решенных головоломок, а time - время работы программы в секундах. Если счет выглядит как: xxx.xxxaaa, то aaa - это количество правильно решенных головоломок.

Пример

Входные данные:
3
..41..3.8.1....62...82..4.....3.28.9....7....7.16.8...562..17.3.3.....4.1....5...
1.......4....1.38.27.9.4...91.7...........5..86.4.5.9..3......8..9....2.4.......7
7..25..98..6....1....61.3..9....1.......8.4.9..75.28.1.94..3.......4923.61.....4.

Выходные данные:
Y
294167358315489627678253491456312879983574216721698534562941783839726145147835962
Y
198563274654217389273984615915726843347198562862435791731642958589371426426859137 
N

Начисление очков:
В данном случае total_solved = 2, положим также что программа работала 10 секунд.
В этом случае количество очков полученных за программу будет равно 1.905002