One rainy afternoon Johnny tought his little sister Mary how to play Tic-Tac-Toe. For those of you who forgot how to play it, here is a short introduction: On a piece of paper, four lines are drawn, two horizontal and two vertical, so that a 3 by 3 grid is formed. Now the two players take turn in placing their mark, a cross for one player and a circle for the other, into one of the grid squares. The player who first places three of his marks in a row, vertical, horizontal or diagonal, wins the game. If nine marks are placed without any player having three in a row, the game ends in a draw. In this problem we’ll let Johnny play with crosses and Mary play with circles. In the picture we see the consectutive stages of a game that Mary started and that was won by Johnny. | | | | | |X | |X | |X | |X X| |X X| |X X|X|X --+---+-- --+---+-- --+---+-- --+---+-- --+---+-- --+---+-- --+---+-- --+---+-- --+---+-- || || || || || ||O ||O |O|O |O|O --+---+-- --+---+-- --+---+-- --+---+-- --+---+-- --+---+-- --+---+-- --+---+-- --+---+-- | | O| | O| | O| O | O| O |X O| O |X O| O |X O| O |X O| O |X At first Johnny was winning this game all the time, but then Mary gradualy improved her tactics and soon all games ended in draw. This is not so exciting, of course, so they invented a more interesting variation on the game. In stead of playing one game at the time, they drew a number of game fields, each on a separate piece of paper. On some of the game fields they put crosses and circles, an equal number of both, taking care that none of them had three in a row. Then they divided the game fields between them: first Johnny selected one, then Mary, then Johnny again, etc., until all were divided. The number of game fields was even, so they both ended up with the same number of games. In the next stage of the game, Mary starts by selecting one of her games and putting a circle on it. If the game is won because there are three circles in a row, Mary scores one point and the paper is discarded. If there are still open places left on the game field, she passes the paper to Johnny, who adds it to his pile of games. If the game is a draw it is simply discarded and noone scores a point. Now it is Johnny’s turn to select a game from his pile and put a cross on it. If the game is won, he scores a point, if there are still open places, he passes the game to Mary. Now it’s Mary’s turn again and this continues until all games are finished. If a player (temporarily) has no more games on his pile when it is his turn, the other player continues playing, until he passes a paper or all the games are finished. The goal of this new game is, of course, to score more points than your opponent. If the scores are equal, the game ends in a draw. Input The input contains several cases. Each case starts with an even number n (2 ≤ n ≤ 1000), the number of game fields in the initial pile. Then follow n lines with 9 characters each, denoting the game field in row major order from top to bottom. Crosses are represented by a capital ‘X’, circles by a capital ‘O’, and empty places by a dot ‘.’. The fifth field in the picture above would be denoted by ‘..X...OOX’. Every field in the input contains equal amounts of circles and crosses, and none has three in a row. The input is ended by a line containing the number 0. Output For each case in the input, one of three lines: ‘Case < n >: Johnny wins.’, if Johnny wins;
2/2 ‘Case < n >: Mary wins.’, if Mary wins; ‘Case < n >: Draw.’, if neither wins; when both players play an optimal strategy. < n > is to be replaced by the case number, starting from
Sample Input 2 ......... ......... 4 XO.X..O.. ....X...O XXO.O.X.O X.O...O.X 2 ......... .X..O..XO 0 Sample Output Case 1: Draw. Case 2: Johnny wins. Case 3: Mary wins.