SP10646 MYQ8 - The National Game

Prasanna and Nithin had mastered Thuvax's national game, [TicTacToe](http://en.wikipedia.org/wiki/Tic-tac-toe). TicTacToe is a board game for two players, x and o, who take turns (alternatively) marking the spaces in a 3×3 grid with their signs 'x' and 'o' respectively. The x player goes first. The player who succeeds in placing three of his signs in a horizontal, vertical, or diagonal row wins the game and the game stops there. While returning from a TicTacToe tournament, Prasanna and Nithin find a tictactoe like grid. They decide to continue playing from the state the board was in. Help Nithin find whether the next person to move will win/lose or whether the game will result in a tie (assuming both players play optimally), or if such a state is invalid.

First line of the input contains a number T (1

Print win/lose/tie/invalid for each testcase on a separate line.