题目背景

万籁停吹奏 $\newline$支颐听秋水问蜉蝣 $\newline$既玄冥不可量北斗 $\newline$却何信相思最温柔

题目描述

象棋将会由两个玩家进行游玩，其中红方为先手，黑方为后手。象棋里有很多种棋子，PF 对其中的“炮”情有独钟，炮的操作为：如果任意一方的某个炮和对方的某个炮之间的位置上有且仅有一个炮，那么这一方可以将对方的炮移出棋盘，并将他的炮移到对方的炮的位置。

PF 厌倦了传统象棋的玩法，因此他拿出了一张 $1$ 行 $n$ 列的棋盘。棋盘上的每个位置都有且仅有一个炮，每个炮都隶属于红方或黑方。对于每个回合，操作方可以进行一次操作，也可以不进行操作，然后将操作权交给对手。若双方均同意结束或者无棋可动，游戏结束。

游戏将进行 $T$ 局。每一局 PF 都是红方。定义游戏的胜利条件为一方的剩余的炮的数量大于对方。他想知道，若双方均使用最佳策略，他是否有必胜策略。

输入格式

第一行一个整数 $T$，表示测试数据的数量。

对于每组数据，第一行一个整数 $n$，表示棋盘大小。

接下来一行一个字符串，其中第 $i$ 个整数 $a_i$ 表示第 $i$ 个棋子的种类，其中 $1$ 表示红方的炮， $0$ 表示黑方的炮。

输出格式

输出共 $T$ 行，若第 $i$ 组有必胜策略，输出 WIN，若为平局输出 TIE，否则输出 LOSE。

4
3
101
5
01100
5
01110
4
1000

WIN
TIE
WIN
LOSE

提示

由于本题输入量较大，请使用较快的读入方法。

【数据范围】

本题采用捆绑测试。

对于 $100\%$ 的数据， $1\le T \le 10^5$，$1 \le n \le 10^7$，$\sum n \le 2\times 10^7$，$a \in \{0,1\}$。

【样例解释】

对于第一组数据，没有任何棋子能够移动，而棋面红棋子数大于黑棋，故先手有必胜策略。

对于第二组数据，一种平局的变化如下：

0 1 1* 0 0*
0 1 0 1

对于第三组数据，双方的最佳策略有如下两种可能：

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

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

两种结果均为红炮剩余数量多，故红棋必胜。

对于第四组数据，红棋只有一种操作可行：

1* 0 0* 0
0 1 0

无棋可走后黑炮数量更多。