The name "Sudoku" is the Japanese abbreviation of a longer phrase, "suji wa dokushin ni kagiru", meaning "the digits must occur only once". Sudoku is a logic-based number placement puzzle. The objective is to fill a 9x9 grid so that each column, each row, and each of the nine 3x3 boxes contains the digits from 1 to 9. The puzzle setter provides a partially completed grid.

Unlike in magazines and newspapers, the digital representation of Sudoku a puzzle is a string of length 81, with all rows of the puzzle placed one after another. The representation uses ASCII symbols ‘1’-‘9’ for digits and ‘.’ for an empty space. For example, the puzzle from figure above can be represented as:

7..25..98..6....1....61.3..9....1.......8.4.9..75.28.1.94..3.......4923.61.....4.

In this task you are to solve such puzzles automatically. The score will depend on the number of solved puzzles and on the speed of your solution. Some of the puzzles have multiple possible solutions, so be careful. A solution is correct if it satisfies the given puzzle. You can be sure that all given Sudokus are correct.

Input

t – the number of test cases; then t test cases follows. [t <= 500]
Each test case describes one SuDoku puzzle and consists of an 81-character-long string.

Output

For the i-th test case output a line containing Y if you want to solve the test case or N if you wish to leave it out. If you chose to solve the test case, in the next line output a sequence of exactly 81 characters corresponding to the solution for the i-th Sudoku puzzle.

Score

The score for this task calculated using the formula: score = 200*total_solved/(200+time), where total_solved - number of correctly solved puzzles, time - running time of your program. If the score has the following form: xxx.xxxaaa, then aaa - is the number of correctly solved puzzles.

Example

Input:
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.

Output:
Y
294167358315489627678253491456312879983574216721698534562941783839726145147835962
Y
198563274654217389273984615915726843347198562862435791731642958589371426426859137 
N

Score:
In this case total_solved = 2. If the program runs for 10 seconds, 
then the score of this solution will be equal to 1.905002

---

hide comments

< Previous 1 2 Next >
	farter yang: 2020-12-24 13:01:18 4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4...... ..............3.85..1.2.......5.7.....4...1...9.......5......73..2.1........4...9 .....5.8....6.1.43..........1.5........1.6...3.......553.....61........4......... 9..8...........5............2..1...3.1.....6....4...7.7.86.........3.1..4.....2.. try adding these cases. best to add another challenge problem that asks to construct a "hardest" puzzle for standard straightforward backtracking algorithm~ Last edit: 2020-12-24 14:29:33
	Edwin Mourant: 2015-10-20 01:53:06 I'd like to offer this problem in a contest that I am setting up. Would it be possible to allow this problem to be "Available for use in 3rd party contests"?
	Francky: 2014-11-22 22:15:50 It seems time limit had been changed from 29s (???) to 24.05s. (pyramid -> cube) (reply by Mitch) Previous time limit was actually 30s. Last edit: 2014-11-22 23:00:50
	Mitch Schwartz: 2014-01-03 23:31:25 @New_Bullet: Try C++ 4.0.0-8.
	New_Bullet: 2014-01-03 23:00:39 Shoot!!!! Y not c++ 4.3.2!!!! I completed the problem using it & am not able to submit it now! @Roman Sol Could C++ be added to the language list pls?
	Bruno Cipolla Moreira: 2013-05-25 23:26:42 Graph Coloration?
	Francky: 2013-03-07 09:10:22 @Michael : No it wasn't intentioned. When you set a problem, you can choose to un-check "Include new language", that was done here (I think), and C++4.3.2 came after that, as other next to.
	Michael Kharitonov: 2013-03-07 08:23:51 Why except C++ 4.3.2? Is there any native sudoku routines in it? Last edit: 2013-03-07 08:24:22
	:D: 2012-08-14 22:07:00 You can submit all you want. Only the best score will be counted.
	Atul Vaibhav: 2012-08-14 08:56:24 Can I re-submit with a different algo to get more points ?