Description

Chinese chess is played by two players, where Red moves first and Black moves second. There are many kinds of pieces in Chinese chess. PF especially likes the "cannon". The cannon move is:

If, for a cannon of one side and a cannon of the opponent, there is exactly one cannon between their positions, then this side may move the opponent's cannon off the board, and move their own cannon to the opponent cannon's position.

PF is tired of the traditional way of playing Chinese chess, so he takes out a board with $1$ row and $n$ columns. Each position on the board has exactly one cannon, and each cannon belongs to Red or Black. In each turn, the player to move may perform one move, or choose not to move, and then pass the turn to the opponent. If both sides agree to end, or there is no move available, the game ends.

There will be $T$ games. In each game, PF is always Red. Define the winning condition as: one side has more remaining cannons than the other side. He wants to know whether, if both sides use optimal strategies, he has a forced win strategy.

Input Format

The first line contains an integer $T$, representing the number of testdata.

For each test case, the first line contains an integer $n$, representing the board size.

The next line contains a string, where the $i$-th integer $a_i$ represents the type of the $i$-th piece: $1$ means a Red cannon, and $0$ means a Black cannon.

Output Format

Output $T$ lines in total. If the $i$-th test case has a forced win strategy, output WIN. If it is a draw, output TIE. Otherwise, output LOSE.

4
3
101
5
01100
5
01110
4
1000

WIN
TIE
WIN
LOSE

Hint

Since the input size is large, please use a faster input method.

Constraints

This problem uses bundled tests.

For $100\%$ of the data: $1\le T \le 10^5$, $1 \le n \le 10^7$, $\sum n \le 2\times 10^7$, $a \in \{0,1\}$.

Sample Explanation

For the first test case, no piece can move, and the number of Red pieces is greater than the number of Black pieces, so the first player has a forced win strategy.

For the second test case, one possible draw line is:

0 1 1* 0 0*
0 1 0 1

For the third test case, there are two possible outcomes under optimal play for both sides:

0 1 1* 1 0*
0* 1 1* 1
1 0 1

0* 1 1* 1 0
1 1* 1 0*
1 0 1

In both results, the number of remaining Red cannons is greater, so Red wins.

For the fourth test case, Red has only one feasible move:

1* 0 0* 0
0 1 0

After no moves remain, Black has more cannons.

Translated by ChatGPT 5