Prasanna and Nithin had mastered Thuvax's national game, Tic-Tac-Toe.

Tic-Tac-Toe 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 Tic-Tac-Toe tournament, Prasanna and Nithin find a Tic-Tac-Toe 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.

Input

First line of the input contains a number T (1 ≤ T ≤ 10⁶), followed by 4×T lines. The first line of each test case is empty and the next 3 lines show the state of the game.

Output

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

Example

Input:
3

oox
.x.
..x

xox
xoo
oxx

o..
...
...

Output:
lose
tie
invalid

Explanation

Case 1: Player x can win by placing x in either last cell of the middle row, or the first cell of the last row. So the next player, o, cannot prevent him from winning from this state.

Case 2: It is completed game, as you can see no one has won. So, it has ended in a tie.

Case 3: Player x should have started the game. Hence such a state can never be reached.