Read problem statements in [Hindi], [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

Chef has no work to do in the kitchen, so he decided to play a card game with the following rules:
Initially, $N$ cards are placed in a row on a table. Each card is placed either face up or face down.
The goal of the game is to remove all cards from the table, one by one.
A card may be removed only if it is currently facing up.
When a card is removed, its adjacent cards (the cards directly to its left and right, if they exist) are flipped, i.e. a card that was facing up will be facing down and vice versa.
There is an empty space left behind each removed card, i.e. the remaining cards are not moved to create a contiguous row of cards again. Therefore, if the game starts with three cards and the middle card is removed, then the cards on the sides are flipped, but removing one of these cards afterwards does not cause the other card to be flipped, since it is only adjacent to the empty space created by removing the middle card.

Determine whether Chef is able to win this game.

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains a single string $S$ describing the row of cards initially placed on the table. Each character of this string is either '1', denoting a face up card, or '0', denoting a face down card.

------  Output ------
For each test case, print a single line containing the string "WIN" if Chef can win the game or "LOSE" if he cannot win (without quotes).

------  Constraints  ------
$1 ≤ T ≤ 10^{2}$
$1 ≤ |S| ≤ 10^{5}$

------  Subtasks ------
Subtask #1 (30 points):
$1 ≤ T ≤ 10$
$1 ≤ |S| ≤ 100$

Subtask #2 (70 points): original constraints

----- Sample Input 1 ------ 
1

10
----- Sample Output 1 ------ 
WIN
----- explanation 1 ------ 
Example case 1: First, Chef should remove the first card, which makes the second card face up. Then, he should remove the second card. This way, all cards are removed and Chef wins.

Difficulty: MEDIUM
Tags: Constructive algorithms

Ad-hoc

Starter code:

Solutions:
o = 20
k = 30
kk = -1
n = int(input())
for _ in range(n):
	str = input()
	col = 0
	for i in str:
		if i == '1':
			col += 1
	if col % 2 == 1:
		print('WIN')
	else:
		print('LOSE')


t = int(input())
for _ in range(t):
	s = input()
	c = 0
	for i in s:
		if i == '1':
			c = c + 1
	if c % 2 == 1:
		print('WIN')
	else:
		print('LOSE')


t = int(input())
for _ in range(t):
	s = input()
	if s.count('1') % 2 == 1:
		print('WIN')
	else:
		print('LOSE')


for _ in range(int(input())):
	s = input()
	(one, zero) = (s.count('1'), s.count('0'))
	if one & 1 == 1:
		print('WIN')
	else:
		print('LOSE')


t = input()
for c in range(0, int(t)):
	s = input()
	(one, zero) = (s.count('1'), s.count('0'))
	if one & 1 == 1:
		print('WIN')
	else:
		print('LOSE')


for t in range(int(input())):
	s = list(map(str, input()))
	c = s.count('1')
	if c % 2 == 0:
		print('LOSE')
	else:
		print('WIN')


for _ in range(int(input())):
	S = input()
	print('WIN' if S.count('1') % 2 == 1 else 'LOSE')


for _ in range(int(input())):
	s = input()
	val = s.count('1')
	res = 'WIN' if val % 2 != 0 else 'LOSE'
	print(res)


t = int(input())
for i in range(t):
	z = input()
	if z.count('1') % 2 == 1:
		print('WIN')
	else:
		print('LOSE')


for i in range(int(input())):
	s = input()
	if s.count('1') % 2 == 1:
		print('WIN')
	else:
		print('LOSE')


T = int(input())
for x in range(T):
	tim = 0
	joyce = input()
	for j in joyce:
		if j == '1':
			tim += 1
	if tim % 2 == 1:
		print('WIN')
	else:
		print('LOSE')


for i in range(int(input())):
	o = z = 0
	seq = input()
	for j in range(len(seq)):
		if seq[j] == '1':
			o += 1
		else:
			z += 1
	if o % 2 == 1:
		print('WIN')
	else:
		print('LOSE')


def check_game(s):
	c = 0
	for i in s:
		if i == '1':
			c += 1
	if c % 2 != 0:
		return 'WIN'
	else:
		return 'LOSE'
t = int(input())
for i in range(t):
	s = input().strip()
	print(check_game(s))


for _ in range(int(input())):
	n = input().strip()
	count1 = n.count('1')
	if count1 & 1:
		print('WIN')
	else:
		print('LOSE')


for i in range(int(input())):
	S = input()
	S1 = []
	for c in S:
		S1.append(c)
	S1 = [int(i) for i in S1]
	if S1.count(1) % 2 == 0:
		print('LOSE')
	else:
		print('WIN')


tests = int(input())
for i in range(tests):
	string = input()
	ones_count = string.count('1')
	if ones_count % 2 == 0:
		print('LOSE')
	else:
		print('WIN')


test_cases = int(input())
for i in range(test_cases):
	one = zero = 0
	seq = input()
	for j in range(len(seq)):
		if seq[j] == '1':
			one += 1
		else:
			zero += 1
	if one % 2 == 1:
		print('WIN')
	else:
		print('LOSE')


import itertools
t = int(input())
while t:
	t -= 1
	s = input()
	gr = [len(list(g)) for (k, g) in itertools.groupby(sorted(s))]
	if gr[0] % 2 == 0 and len(s) % 2 != 0 or (gr[0] % 2 != 0 and len(s) % 2 == 0):
		print('WIN')
	else:
		print('LOSE')


for T in range(int(input())):
	s = str(input())
	o = s.count('1')
	if o % 2 == 0:
		print('LOSE')
	else:
		print('WIN')


from functools import reduce
for _ in range(int(input())):
	print('WIN' if reduce(int.__xor__, (c == '1' for c in input())) else 'LOSE')


t = int(input())
while t > 0:
	s = input()
	t -= 1
	a = 0
	for i in range(0, len(s)):
		if s[i] == '1':
			a += 1
	if a % 2 == 1:
		print('WIN')
	else:
		print('LOSE')


for _ in range(int(input())):
	s = input()
	s = list(s)
	if len(s) == 1 and s == '1':
		print('WIN')
		continue
	if s.count('1') % 2 != 0:
		print('WIN')
	else:
		print('LOSE')


for _ in range(int(input())):
	s = list(input())
	k = s.count('1')
	if k % 2 == 1:
		print('WIN')
	else:
		print('LOSE')


t = int(input())
for k in range(t):
	s = str(input())
	cnt = 0
	for m in range(0, len(s)):
		if s[m] == '1':
			cnt += 1
	if cnt % 2 == 1:
		print('WIN')
	else:
		print('LOSE')


t = int(input())
for j in range(t):
	a = input()
	c = 0
	for i in a:
		if i == '1':
			c += 1
	if c % 2 == 1:
		print('WIN')
	else:
		print('LOSE')


for i in range(0, int(input())):
	c = 0
	s = list(input())
	for e in s:
		c += 1 if e == '1' else 0
	print('WIN' if c % 2 == 1 else 'LOSE')


for _ in range(int(input())):
	s = list(input())
	s.append('1')
	(n1, n2) = (0, 0)
	l = len(s)
	for j in range(l - 1):
		if s[j] == '0':
			n1 += 1
		if s[j] == '1':
			n2 += n1 + 1
			n1 = 0
			if s[j + 1] == '1':
				s[j + 1] = '0'
			else:
				s[j + 1] = '1'
	if n2 == l - 1:
		print('WIN')
	else:
		print('LOSE')


for i in range(int(input())):
	x = input()
	if x.count('1') % 2 == 0:
		print('LOSE')
	else:
		print('WIN')


import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	s = input()
	if s.count('1') % 2 == 0:
		print('LOSE')
	else:
		print('WIN')


t = int(input())
while t != 0:
	s = input()
	if s.count('1') % 2 != 0:
		print('WIN')
	else:
		print('LOSE')
	t -= 1


t = int(input())
for _ in range(t):
	s = input()
	ans = 0
	for i in s:
		ans = ans ^ int(i)
	if ans:
		print('WIN')
	else:
		print('LOSE')


b = int(input())
for i in range(b):
	a = input()
	if a.count('1') % 2 != 0:
		print('WIN')
	else:
		print('LOSE')


T = int(input(''))
for i in range(T):
	S = input('')
	if S.count('1') % 2 == 1:
		print('WIN')
	else:
		print('LOSE')


def solve():
	s = input()
	if s.count('1') % 2 == 1:
		return 'WIN'
	else:
		return 'LOSE'
t = int(input())
while t:
	print(solve())
	t -= 1


def siva():
	n = input()
	k = n.count('1')
	if k % 2 == 1:
		print('WIN')
		return
	print('LOSE')
	return
try:
	s = int(input())
	for i in range(s):
		siva()
except:
	pass


def solve():
	s = input()
	a = s.count('1')
	if a % 2 == 1:
		print('WIN')
		return
	print('LOSE')
	return
try:
	t = int(input())
	for i in range(t):
		solve()
except:
	pass


t = int(input())
while t > 0:
	c = 0
	l = input()
	for i in l:
		if i == '1':
			c += 1
	if c % 2 == 0:
		print('LOSE')
	else:
		print('WIN')
	t -= 1


t = int(input())
while t:
	t -= 1
	n = input()
	a = n.count('1')
	if a % 2 == 0:
		print('LOSE')
	else:
		print('WIN')


for i in range(int(input())):
	n = str(input())
	m = list(n)
	ans = m.count('1')
	if ans % 2 == 0:
		print('LOSE')
	else:
		print('WIN')


t = int(input())
for i in range(t):
	s = str(input())
	if s.count('1') % 2 == 0:
		print('LOSE')
	else:
		print('WIN')


import sys
import math

def main(arr):
	i = len(arr) - 1
	removed = 0
	while i != -1:
		if arr[i] == 1:
			arr[i] = 0
			if i != 0:
				arr[i - 1] = arr[i - 1] ^ 1
			removed = len(arr) - i
		i -= 1
	if removed != len(arr):
		print('LOSE')
	else:
		print('WIN')
	return
for _ in range(int(input())):
	arr = list(map(int, input()))
	main(arr)


for _ in range(int(input())):
	print('LOSE' if list(input().strip()).count('1') % 2 == 0 else 'WIN')


t = int(input())
for i in range(t):
	s = input()
	list1 = []
	for i in s:
		list1.append(i)
	c = 0
	for j in list1:
		if j == '1':
			c += 1
	if c % 2 != 0:
		print('WIN')
	else:
		print('LOSE')


test = int(input())
for i in range(test):
	c = 0
	v = input()
	l = list(v)
	for i in l:
		if int(i) == 1:
			c += 1
	if c % 2 != 0:
		print('WIN')
	else:
		print('LOSE')


t = int(input())
for _ in range(t):
	N = input()
	CardLst = [int(x) for x in str(N)]
	z = CardLst.count(1)
	if z % 2 == 0:
		print('LOSE')
	else:
		print('WIN')


t = int(input())
while t > 0:
	a = list(input())
	c = a.count('1')
	if c % 2 != 0:
		print('WIN')
	else:
		print('LOSE')
	t -= 1


test = int(input())
while test > 0:
	a = input()
	count = 0
	for x in a:
		if x == '1':
			count = count + 1
	if count % 2 == 0:
		print('LOSE')
	else:
		print('WIN')
	test = test - 1


t = int(input())
for i in range(t):
	s = list(input())
	n = len(s)
	c = s.count('1')
	if c % 2 == 1:
		print('WIN')
	else:
		print('LOSE')