Bowling is a sport in which a player rolls a bowling ball towards a group of pins, the target being to knock down the pins at the end of a lane.

In this challenge, the rules of the game are slightly modified. Now, there are a given number of pins, and the pins are arranged in a horizontal line instead of a triangular formation. Two players have to play this game, taking alternate turns. Whoever knocks down the last pin(s) will be declared the winner.  

You are playing this game with your friend, and both of you have become proficient at it. You can knock down any single pin, or any two adjacent pins at one throw of a bowling ball, however, these are the only moves that you can perform. Some moves have already been played. Suddenly, you realize that it is possible to determine whether this game can be won or not, assuming optimal play. And luckily it's your turn right now.  

A configuration is represented by a string consisting of the letters X and I, where: 

I represents a position containing a pin.
X represents a position where a pin has been knocked down.

An example of such a configuration is shown in the image below. Here, the number of pins is $13$, and the $2^{\text{nd}}$ pin has already been knocked down.  

Its representation will be IXIIIIIIIIIII.

Complete the function isWinning that takes the number of pins and the configuration of the pins as input, and return WIN or LOSE based on whether or not you will win. 

Given the current configuration of the pins, if both of you play optimally, determine whether you will win this game or not. 

Note   

A player has to knock down at least one pin in his turn.
Both players play optimally.  

Input Format

The first line contains an integer, $\boldsymbol{\boldsymbol{t}}$, the number of test cases. Then $\boldsymbol{\boldsymbol{t}}$ test cases follow.  

For each test case, the first line contains a single integer $n$, denoting the number of pins. The second line contains a string of $n$ letters, where each letter is either I or X.  

Constraints

$1\leq t\leq1000$  
$1\leq n\leq300$  
Each letter of the string (representing the configuration) is either I or X.  
There will be at least one I in the string.  

Output Format

For each test case, print a single line containing WIN if you will win this game, otherwise LOSE.  

Sample Input 0
4
4
IXXI
4
XIIX
5
IIXII
5
IIIII

Sample Output 0
LOSE
WIN
LOSE
WIN

Explanation 0

Test Case 1: As the $2$ pins are not adjacent, they can't be knocked down in a single turn. Therefore, you can only knock down one of the two pins. Then, in the next turn, your friend will knock down the last pin.

Test Case 2: You can knock down both pins in a single turn.

Test Case 3: You can knock down one or two pins from either side. Your friend can just copy your move on the other side and will be able to get the last move, hence win the game.

Test Case 4: You can knock the middle pin, thus resulting in the configuration IIXII for your friend. Now, this configuration is the same as the previous test case. The difference is that now it is your friend's turn and you can copy his shot on the other side.

Source: hackerrank | Difficulty: MEDIUM_HARD
Tags: Complete search


Solutions:
def game_from(board: str) -> list:
	game = []
	count = 0
	for c in board:
		if c == 'I':
			count += 1
		elif count > 0:
			game.append(count)
			count = 0
	if count > 0:
		game.append(count)
	return game

def moves_for(n: int, hits: [int]) -> [list]:
	moves = []
	for hit in hits:
		left = 0
		right = n - hit
		while left <= right:
			if left == 0 and right == 0:
				continue
			elif right < 1 <= left:
				moves.append([left])
			elif left < 1 <= right:
				moves.append([right])
			else:
				moves.append([left, right])
			left += 1
			right -= 1
	return moves

def mex_of(s: set) -> int:
	mex = 0
	while mex in s:
		mex += 1
	return mex

def g_of(n: int, cache: dict) -> int:
	if n < 3:
		return n
	else:
		result = cache.get(n, None)
		if result is not None:
			return result
		moves = moves_for(n, [1, 2])
		s = set()
		for move in moves:
			if len(move) == 1:
				s.add(g_of(move[0], cache))
			else:
				s.add(g_of(move[0], cache) ^ g_of(move[1], cache))
		result = mex_of(s)
		cache[n] = result
		return result

def winner(board: str, cache: dict) -> str:
	game = game_from(board)
	g = 0
	for i in game:
		g ^= g_of(i, cache)
	return 'WIN' if g != 0 else 'LOSE'
n = int(input().strip())
c = {}
for i in range(n):
	input()
	g = list(input().strip())
	print(winner(g, c))


def get_or_update(key, f):
	if key not in cache:
		cache[key] = f()
	return cache[key]

def replace_at_index(tup, ix, val):
	return tup[:ix] + (val,) + tup[ix + 1:]

def pin_to_nim(pins):
	nim = []
	curr_pile = 0
	for i in range(len(pins)):
		if pins[i]:
			curr_pile += 1
		elif curr_pile > 0:
			nim.append(curr_pile)
			curr_pile = 0
	if curr_pile > 0:
		nim.append(curr_pile)
	return tuple(nim)

def nim_to_pin(nim):
	pin = []
	for x in nim:
		pin.extend([True] * x)
		pin.append(False)
	return tuple(pin[:-1])

def get_new_configs(pins, N):
	new_configs = set()
	for i in range(N):
		if pins[i]:
			new_config = replace_at_index(pins, i, False)
			new_configs.add(new_config)
			if i <= N - 2 and pins[i + 1]:
				new_config = replace_at_index(new_config, i + 1, False)
				new_configs.add(new_config)
	return new_configs

def get_winner(pins, N):
	new_configs = get_new_configs(pins, N)
	if not new_configs:
		return 2
	elif new_configs == {tuple([False] * 5)}:
		return 1
	else:
		next_winners = [get_or_update(config, lambda : get_winner(config, N)) for config in new_configs]
		if any([nw == 2 for nw in next_winners]):
			return 1
		else:
			return 2
grundy_cache = {1: 1, 2: 2}

def get_or_update(key, f):
	if key not in cache:
		cache[key] = f()
	return cache[key]

def get_grundy_number(nbr):
	if nbr in grundy_cache:
		return grundy_cache[nbr]
	else:
		pin_config = nim_to_pin((nbr,))
		n = len(pin_config)
		next_nim_configs = {pin_to_nim(x) for x in get_new_configs(pin_config, n)}
		next_grundys = sorted([get_config_grundy(nnc) for nnc in next_nim_configs])
		mex = 0
		for ng in next_grundys:
			mex = mex + 1 if ng == mex else mex
		grundy_cache[nbr] = mex
		return mex

def get_config_grundy(nim_config):
	rv = 0
	for x in nim_config:
		rv = rv ^ get_grundy_number(x)
	return rv
T = int(input())
for _ in range(T):
	N = int(input())
	pins = tuple([x == 'I' for x in input()])
	cache = dict()
	if get_config_grundy(pin_to_nim(pins)):
		print('WIN')
	else:
		print('LOSE')


cache_dict = {}

def grundy(string):
	length = len(string)
	if length == 0:
		return 0
	elif length == 1 or length == 4:
		return 1
	elif length == 2:
		return 2
	elif length == 3:
		return 3
	if string in cache_dict.keys():
		return cache_dict[string]
	res_1 = set()
	for i in range(len(string)):
		try:
			res_1.add(string[:i] + 'X' + string[i + 1:])
		except:
			pass
		try:
			temp = string[:i] + 'XX' + string[i + 2:]
			if len(temp) == len(string):
				res_1.add(temp)
		except:
			pass
	res_1 = list(res_1)
	for (i, each) in enumerate(res_1):
		new_str = pre(each)
		gr_num = []
		for each1 in new_str:
			gr_num.append(grundy(each1))
		gr_num = xoring(gr_num)
		res_1[i] = gr_num
	res_1 = set(res_1)
	gr_num = mex(res_1)
	cache_dict[string] = gr_num
	return gr_num

def mex(t_list):
	for i in range(10):
		if i not in t_list:
			res = i
			break
	return res

def xoring(t_list):
	res = 0
	for (i, item) in enumerate(t_list):
		if i == 0:
			res = item
			continue
		res = res ^ item
	return res

def pre(string):
	string = string.split('X')
	string = filter(None, string)
	return string
t = int(input())
for test in range(t):
	n = input()
	arr = input()
	arr = pre(arr)
	gr_num = []
	for each in arr:
		gr_num.append(grundy(each))
	gr_num = xoring(gr_num)
	if gr_num > 0:
		print('WIN')
	else:
		print('LOSE')


cache_dict = {}

def grundy(string):
	length = len(string)
	if length == 0:
		return 0
	elif length == 1 or length == 4:
		return 1
	elif length == 2:
		return 2
	elif length == 3:
		return 3
	if string in cache_dict.keys():
		return cache_dict[string]
	res_1 = set()
	for i in range(len(string)):
		try:
			res_1.add(string[:i] + 'X' + string[i + 1:])
		except:
			pass
		try:
			temp = string[:i] + 'XX' + string[i + 2:]
			if len(temp) == len(string):
				res_1.add(temp)
		except:
			pass
	res_1 = list(res_1)
	for (i, each) in enumerate(res_1):
		new_str = pre(each)
		gr_num = []
		for each1 in new_str:
			gr_num.append(grundy(each1))
		gr_num = xoring(gr_num)
		res_1[i] = gr_num
	res_1 = set(res_1)
	gr_num = mex(res_1)
	cache_dict[string] = gr_num
	return gr_num

def mex(t_list):
	for i in range(10):
		if i not in t_list:
			res = i
			break
	return res

def xoring(t_list):
	res = 0
	for (i, item) in enumerate(t_list):
		if i == 0:
			res = item
			continue
		res = res ^ item
	return res

def pre(string):
	string = string.split('X')
	string = filter(None, string)
	return string
t = int(input())
for test in range(t):
	n = input()
	arr = input()
	arr = pre(arr)
	gr_num = []
	for each in arr:
		gr_num.append(grundy(each))
	gr_num = xoring(gr_num)
	if gr_num > 0:
		print('WIN')
	else:
		print('LOSE')


g = [0, 1, 2]
for n in range(3, 301):
	s = set()
	for l in (1, 2):
		for i in range((n - l) // 2 + 1):
			s.add(g[i] ^ g[n - l - i])
	m = 0
	while m in s:
		m += 1
	g.append(m)
for _ in range(int(input())):
	n = int(input())
	sl = input().split('X')
	ret = 0
	for p in sl:
		ret ^= g[len(p)]
	print('WIN' if ret else 'LOSE')


g = {}

def f(n):
	if n < 0:
		return -1
	if n not in g:
		h = set()
		h.add(f(n - 1))
		h.add(f(n - 2))
		for i in range(1, n // 2 + 1):
			h.add(f(i) ^ f(n - i - 1))
			h.add(f(i) ^ f(n - i - 2))
		i = 0
		while i in h:
			i += 1
		g[n] = i
	return g[n]
for _ in range(int(input())):
	x = c = 0
	input()
	for i in input().strip():
		if i == 'I':
			c += 1
		elif c:
			x ^= f(c)
			c = 0
	if c:
		x ^= f(c)
	print('WIN' if x else 'LOSE')


g = [0, 1, 2]
for n in range(3, 301):
	s = set()
	lim = n // 2
	for i in range(lim + 1):
		s.add(g[i] ^ g[n - 1 - i])
	if n % 2 == 0:
		lim = n // 2 - 1
	for i in range(lim + 1):
		s.add(g[i] ^ g[n - 2 - i])
	m = 0
	while m in s:
		m += 1
	g.append(m)
n = int(input())
for i in range(n):
	input()
	s = input().split('X')
	sum = 0
	for l in range(len(s)):
		sum ^= g[len(s[l])]
	if sum == 0:
		print('LOSE')
	else:
		print('WIN')


def sg_function(pins, sg_cache):
	if pins in sg_cache:
		return sg_cache[pins]
	integers = set()
	for p in range((pins - 1) // 2 + 1):
		integers.add(sg_function(p, sg_cache) ^ sg_function(pins - p - 1, sg_cache))
		integers.add(sg_function(p, sg_cache) ^ sg_function(pins - p - 2, sg_cache))
	smallest = 0
	while smallest in integers:
		smallest += 1
	sg_cache[pins] = smallest
	return smallest

def current_player_advantage(pins, cache):
	if pins in cache:
		return cache[pins]
	result_so_far = True
	number_groups = 0
	for p in range(0, (pins + 1) // 2):
		number_groups += 1
		a = current_player_advantage(p, cache)
		b = current_player_advantage(pins - p - 1, cache)
		result_so_far = result_so_far ^ a ^ b
	for p in range(0, pins // 2):
		number_groups += 1
		result_so_far = result_so_far ^ current_player_advantage(p, cache) ^ current_player_advantage(pins - p - 2, cache)
	cache[pins] = result_so_far
	return result_so_far

def parse_groups_pins(pins):
	pins = [len(x) for x in pins.split('X') if len(x) > 0]
	return pins
	result_so_far = False
	for p in pins:
		result_so_far = result_so_far ^ current_player_advantage(p, cache)
	if result_so_far:
		print('WIN')
	else:
		print('LOSE')
g = [0, 1, 2]
for n in range(3, 301):
	s = set()
	for l in (1, 2):
		for i in range((n - l) // 2 + 1):
			s.add(g[i] ^ g[n - l - i])
	m = 0
	while m in s:
		m += 1
	g.append(m)
T = int(input())
sg_cache = {0: 0, 1: 1, 2: 2}
for _ in range(T):
	n = int(input())
	bla = input()
	pins = parse_groups_pins(bla)
	nim_value = 0
	for p in pins:
		nim_value ^= sg_function(p, sg_cache)
	if nim_value != 0:
		print('WIN')
	else:
		print('LOSE')


win = [0]
for n in range(1, 301):
	s = set()
	for a in range(n // 2 + 1):
		s.add(win[a] ^ win[n - 1 - a])
		s.add(win[a] ^ win[n - 2 - a])
	m = 0
	while m in s:
		m += 1
	win.append(m)

def solve(S):
	r = 0
	for s in S.split('X'):
		r ^= win[len(s)]
	return 'WIN' if r else 'LOSE'
T = int(input())
for _ in range(T):
	N = int(input())
	S = input()
	print(solve(S))


from functools import reduce
t = int(input().strip())
test_cases = []
while t > 0:
	t -= 1
	_ = input()
	s = input().strip()
	test_cases.append(s)

class Solution:

	def solver(self, s):
		s = filter(lambda x: x != '', s.split('X'))
		self.mex = {0: 0, 1: 1, 2: 2}
		res = self.helper(s)
		return 'LOSE' if res == 0 else 'WIN'

	def helper(self, s):

		def getRes(t):
			if t in self.mex:
				return self.mex[t]
			else:
				mex_set = set()
				for l in [1, 2]:
					for i in range((t - l) // 2 + 1):
						mex_set.add(getRes(i) ^ getRes(t - i - l))
				r = 0
				while r in mex_set:
					r += 1
				self.mex[t] = r
				return self.mex[t]
		mex_list = list(map(lambda x: getRes(len(x)), s))
		res = reduce(lambda x, y: x ^ y, mex_list)
		return res
sol = Solution()
for test in test_cases:
	print(sol.solver(test))


g = [0, 1, 2]
for n in range(3, 301):
	s = set()
	for l in (1, 2):
		for i in range((n - l) // 2 + 1):
			s.add(g[i] ^ g[n - l - i])
	m = 0
	while m in s:
		m += 1
	g.append(m)
for t in range(int(input())):
	input()
	ret = 0
	for p in input().split('X'):
		ret ^= g[len(p)]
	print('WIN' if ret else 'LOSE')


p = {0: 0, 1: 1, 2: 2, 3: 3}
for i in range(4, 301):
	s = set()
	for j in range(i - 1):
		s.add(p[j] ^ p[i - j - 1])
		s.add(p[j] ^ p[i - j - 2])
	gr = 0
	while gr in s:
		gr += 1
	p[i] = gr
t = int(input())
for ti in range(t):
	n = int(input())
	s = 'X' + input() + 'X'
	a = []
	L = 0
	for i in range(len(s)):
		if s[i] == 'X':
			if i != 0 and L != 0:
				a.append(L)
			L = 0
		else:
			L += 1
	gr = 0
	for i in a:
		gr ^= p[i]
	if gr == 0:
		print('LOSE')
	else:
		print('WIN')


cache = {0: 0, 1: 1}

def grundy(p):
	try:
		return cache[p]
	except KeyError:
		None
	vals = set([])
	for i in range(p // 2 + 1):
		vals.add(grundy(i) ^ grundy(p - i - 1))
	if p >= 2:
		for i in range(p // 2):
			vals.add(grundy(i) ^ grundy(p - i - 2))
	i = 0
	while i in vals:
		i += 1
	cache[p] = i
	return i
T = int(input())
for i in range(T):
	N = int(input())
	pins_str = input()
	pins = [len(s) for s in pins_str.split('X') if s]
	res = 0
	for p in pins:
		res ^= grundy(p)
	if res:
		print('WIN')
	else:
		print('LOSE')


ni = [i for i in range(302)]
for l in range(3, 301):
	s = set()
	for i in range(1, (l + 1) // 2 + 1):
		s.add(ni[l - i] ^ ni[i - 1])
		s.add(ni[l - i - 1] ^ ni[i - 1])
	i = 0
	while i in s:
		i += 1
	ni[l] = i
for _ in range(int(input())):
	l = int(input())
	s = input().split('X')
	ac = 0
	for j in s:
		ac ^= ni[len(j)]
	if ac:
		print('WIN')
	else:
		print('LOSE')


import sys
from functools import reduce

def memoized(func):
	cache = {}

	def newfunc(*args):
		if args not in cache:
			cache[args] = func(*args)
		return cache[args]
	return newfunc

@memoized
def f(n):
	if n < 4:
		return n
	res = set([f(n - 1), f(n - 2)])
	for i in range(1, n - 1):
		res.add(f(i) ^ f(n - i - 1))
		res.add(f(i) ^ f(n - i - 2))
	for i in range(n):
		if i not in res:
			return i
t = int(input().strip())
for a0 in range(t):
	n = int(input().strip())
	config = [f(len(x)) for x in input().strip().split('X') if x]
	result = reduce(lambda x, y: x ^ y, config)
	print('WIN' if result else 'LOSE')


import sys
import re

def isWinning(n, config):
	groups = config.strip().split('X')
	max_len = 0
	for g in groups:
		max_len = max(max_len, len(g))
	g = [0, 1, 2]
	for n in range(3, max_len + 1):
		s = set()
		for l in (1, 2):
			for i in range((n - l) // 2 + 1):
				s.add(g[i] ^ g[n - l - i])
		m = 0
		while m in s:
			m += 1
		g.append(m)
	ret = 0
	for p in groups:
		ret ^= g[len(p)]
	if ret:
		return 'WIN'
	else:
		return 'LOSE'
t = int(input().strip())
for a0 in range(t):
	n = int(input().strip())
	config = input().strip()
	result = isWinning(n, config)
	print(result)


import sys

def isWinning(n, config):
	config_split = config.split('X')
	win = False
	temp = False
	while '' in config_split:
		config_split.remove('')
	v1 = list(range(1, n + 1, 4))
	v2 = [x + 1 for x in v1]
	vw = v1 + v2
	if not config_split:
		return 'WIN'
	for st in config_split:
		if len(st) in vw:
			temp = True
		win = win ^ temp
	if win:
		return 'WIN'
	else:
		return 'LOSE'

def isWin(g, config):
	ret = 0
	for p in config.split('X'):
		ret ^= g[len(p)]
	if ret:
		return 'WIN'
	else:
		return 'LOSE'
g = [0, 1, 2]
for n1 in range(3, 301):
	s = set()
	for l in (1, 2):
		for i in range(int((n1 - l) / 2) + 1):
			s.add(g[i] ^ g[n1 - l - i])
	m = 0
	while m in s:
		m += 1
	g.append(m)
t = int(input().strip())
for a0 in range(t):
	n = int(input().strip())
	config = input().strip()
	result = isWin(g, config)
	print(result)


def config2NumArray(config):
	strings = config.split('X')
	return [len(s) for s in strings if s != '']

def isWinning(n, config):
	n = nimber(config2NumArray(config))
	if n == 0:
		return 'LOSE'
	else:
		return 'WIN'
nimbers = {}

def mex(values):
	value_set = set(values)
	for i in range(len(values) + 1):
		if i not in value_set:
			return i

def nimber(game):
	if len(game) == 1:
		value = game[0]
		if value == 0:
			return 0
		if value in nimbers:
			return nimbers[value]
		else:
			results = []
			for i in range((value + 1) // 2):
				results.append(nimber([value - i - 1, i]))
			for i in range(value // 2):
				results.append(nimber([value - i - 2, i]))
			my_nimber = mex(results)
			nimbers[value] = my_nimber
			return my_nimber
	nimber_xor = 0
	for i in game:
		nimber_xor ^= nimber([i])
	return nimber_xor
t = int(input().strip())
for a0 in range(t):
	n = int(input().strip())
	config = input().strip()
	result = isWinning(n, config)
	print(result)


g = [0, 1, 2]
for n in range(3, 301):
	s = set()
	for l in (1, 2):
		for i in range((n - l) // 2 + 1):
			s.add(g[i] ^ g[n - l - i])
	m = 0
	while m in s:
		m += 1
	g.append(m)
for _ in range(int(input())):
	input()
	r = 0
	for p in input().split('X'):
		r ^= g[len(p)]
	print('WIN' if r else 'LOSE')


import sys
from time import time
cache = dict()

def f(groups):
	if groups in cache:
		return cache[groups]
	rval = False
	(cnt, total) = (0, 0)
	for (i, c) in enumerate(groups):
		if c:
			cnt += 1
			total += c
	if cnt == 1:
		rval = total % 2 == 1
	elif cnt > 1:
		keepgoing = True
		for (sz, cnt) in enumerate(groups):
			if not keepgoing:
				break
			if not cnt:
				continue
			for d in (1, 2):
				if not keepgoing:
					break
				for i in range((sz - d) // 2 + 1):
					(sz_l, sz_r) = (i, sz - d - i)
					new_groups = list(groups)
					new_groups[sz] -= 1
					new_groups[sz_l] += 1
					new_groups[sz_l] %= 2
					new_groups[sz_r] += 1
					new_groups[sz_r] %= 2
					new_groups[0] = 0
					new_groups = tuple(new_groups)
					if not f(new_groups):
						rval = True
						keepgoing = False
	cache[groups] = rval
	return rval

def groups_gen(s):
	cnt = 0
	for c in s:
		if c == 'I':
			cnt += 1
		elif cnt:
			yield cnt
			cnt = 0
	if cnt:
		yield cnt

def solve_bf(s):
	(groups, mx) = (dict(), 0)
	for d in groups_gen(s):
		mx = max(mx, d)
		if d in groups:
			groups[d] += 1
		else:
			groups[d] = 1
	groups = tuple((i in groups and groups[i] % 2 or 0 for i in range(mx + 1)))
	return f(groups)

def nimber_gen():

	def mex(cache):
		r = 0
		while r in cache:
			r += 1
		return r
	(nn, cache) = ([0], set())
	for n in nn:
		yield n
	(sz, r) = (0, 0)
	while True:
		sz += 1
		cache.clear()
		print('\tsz=%d nn=%s' % (sz, nn), file=sys.stderr)
		for d in (1, 2):
			print('\t\td=%d' % (d,), file=sys.stderr)
			for i in range((sz - d) // 2 + 1):
				(sz_l, sz_r) = (i, sz - d - i)
				print('\t\t\tsz_l=%d sz_r=%d' % (sz_l, sz_r), file=sys.stderr)
				u = nn[sz_l] ^ nn[sz_r]
				cache.add(u)
		print('\tcache=%s' % (sorted(cache),), file=sys.stderr)
		r = mex(cache)
		nn.append(r)
		yield r

def solve(s):
	print('s=%s' % s, file=sys.stderr)
	(groups, mx) = (dict(), 0)
	for d in groups_gen(s):
		mx = max(mx, d)
		if d in groups:
			groups[d] += 1
		else:
			groups[d] = 1
	nn = []
	for (sz, n) in enumerate(nimber_gen()):
		nn.append(n)
		if sz == mx:
			break
	print('\tnn=%s' % nn, file=sys.stderr)
	rval = 0
	for (sz, cnt) in groups.items():
		if cnt % 2 == 1:
			n = nn[sz]
			rval ^= n
			print('\tsz=%d cnt=%d n=%d' % (sz, cnt, n), file=sys.stderr)
	return rval
tm = time()
t = int(input())
for _ in range(t):
	_ = int(input())
	s = input()
	if solve(s):
		print('WIN')
	else:
		print('LOSE')
print('time elapsed: %s' % (time() - tm,), file=sys.stderr)


g = [0, 1, 2]
for n in range(3, 301):
	s = set()
	for l in (1, 2):
		for i in range((n - l) // 2 + 1):
			s.add(g[i] ^ g[n - l - i])
	m = 0
	while m in s:
		m += 1
	g.append(m)
for t in range(int(input().strip())):
	input()
	ret = 0
	for p in input().strip().split('X'):
		ret ^= g[len(p)]
	print('WIN' if ret else 'LOSE')


g = [0, 1, 2]
for n in range(3, 301):
	s = set()
	lim = n // 2
	for i in range(lim + 1):
		s.add(g[i] ^ g[n - 1 - i])
	if n % 2 == 0:
		lim = n // 2 - 1
	for i in range(lim + 1):
		s.add(g[i] ^ g[n - 2 - i])
	m = 0
	while m in s:
		m += 1
	g.append(m)
n = int(input())
for i in range(n):
	input()
	s = input().split('X')
	sum = 0
	for l in range(len(s)):
		sum ^= g[len(s[l])]
	if sum == 0:
		print('LOSE')
	else:
		print('WIN')


def game_from(board: str) -> list:
	game = []
	count = 0
	for c in board:
		if c == 'I':
			count += 1
		elif count > 0:
			game.append(count)
			count = 0
	if count > 0:
		game.append(count)
	return game

def moves_for(n: int, hits: [int]) -> [list]:
	moves = []
	for hit in hits:
		left = 0
		right = n - hit
		while left <= right:
			if left == 0 and right == 0:
				continue
			elif right < 1 <= left:
				moves.append([left])
			elif left < 1 <= right:
				moves.append([right])
			else:
				moves.append([left, right])
			left += 1
			right -= 1
	return moves

def mex_of(s: set) -> int:
	mex = 0
	while mex in s:
		mex += 1
	return mex

def g_of(n: int, cache: dict) -> int:
	if n < 3:
		return n
	else:
		result = cache.get(n, None)
		if result is not None:
			return result
		moves = moves_for(n, [1, 2])
		s = set()
		for move in moves:
			if len(move) == 1:
				s.add(g_of(move[0], cache))
			else:
				s.add(g_of(move[0], cache) ^ g_of(move[1], cache))
		result = mex_of(s)
		cache[n] = result
		return result

def winner(board: str, cache: dict) -> str:
	game = game_from(board)
	g = 0
	for i in game:
		g ^= g_of(i, cache)
	return 'WIN' if g != 0 else 'LOSE'
n = int(input().strip())
c = {}
for i in range(n):
	input()
	g = list(input().strip())
	print(winner(g, c))


win = [0]
for n in range(1, 301):
	s = set()
	for a in range(n // 2 + 1):
		s.add(win[a] ^ win[n - 1 - a])
		s.add(win[a] ^ win[n - 2 - a])
	m = 0
	while m in s:
		m += 1
	win.append(m)

def solve(S):
	ret = 0
	for S in input().strip().split('X'):
		ret ^= win[len(S)]
	print('WIN' if ret else 'LOSE')
for t in range(int(input().strip())):
	input()
	ret = 0
	for p in input().strip().split('X'):
		ret ^= win[len(p)]
	print('WIN' if ret else 'LOSE')


def game_from(board: str) -> list:
	game = []
	count = 0
	for c in board:
		if c == 'I':
			count += 1
		elif count > 0:
			game.append(count)
			count = 0
	if count > 0:
		game.append(count)
	return game

def moves_for(n: int, hits: [int]) -> [list]:
	moves = []
	for hit in hits:
		left = 0
		right = n - hit
		while left <= right:
			if left == 0 and right == 0:
				continue
			elif right < 1 <= left:
				moves.append([left])
			elif left < 1 <= right:
				moves.append([right])
			else:
				moves.append([left, right])
			left += 1
			right -= 1
	return moves

def mex_of(s: set) -> int:
	mex = 0
	while mex in s:
		mex += 1
	return mex

def g_of(n: int, cache: dict) -> int:
	if n < 3:
		return n
	else:
		result = cache.get(n, None)
		if result is not None:
			return result
		moves = moves_for(n, [1, 2])
		s = set()
		for move in moves:
			if len(move) == 1:
				s.add(g_of(move[0], cache))
			else:
				s.add(g_of(move[0], cache) ^ g_of(move[1], cache))
		result = mex_of(s)
		cache[n] = result
		return result

def winner(board: str, cache: dict) -> str:
	game = game_from(board)
	g = 0
	for i in game:
		g ^= g_of(i, cache)
	return 'WIN' if g != 0 else 'LOSE'
n = int(input().strip())
c = {}
for i in range(n):
	input()
	g = list(input().strip())
	print(winner(g, c))


import os
import sys
g = [0, 1, 2]
for n in range(3, 301):
	s = set()
	for l in (1, 2):
		for i in range(int((n - l) / 2) + 1):
			s.add(g[i] ^ g[n - l - i])
	m = 0
	while m in s:
		m += 1
	g.append(m)
for t in range(int(input().strip())):
	input()
	ret = 0
	for p in input().strip().split('X'):
		ret ^= g[len(p)]
	print('WIN' if ret else 'LOSE')


def mex(S):
	x = 0
	while x in S:
		x += 1
	return x
memo = {0: 0}

def grundy(n):
	if n not in memo:
		S = set()
		for i in range(n):
			S.add(grundy(i) ^ grundy(n - 1 - i))
			if i < n - 1:
				S.add(grundy(i) ^ grundy(n - 2 - i))
		memo[n] = mex(S)
	return memo[n]
t = int(input())
for _ in range(t):
	n = int(input())
	C = input().split('X')
	g = 0
	for B in C:
		g ^= grundy(len(B))
	print('LOSE' if g == 0 else 'WIN')


import os
import sys
win = [0]
for n in range(1, 301):
	s = set()
	for a in range(n // 2 + 1):
		s.add(win[a] ^ win[n - 1 - a])
		s.add(win[a] ^ win[n - 2 - a])
	m = 0
	while m in s:
		m += 1
	win.append(m)

def solve(S):
	r = 0
	for s in S.split('X'):
		r ^= win[len(s)]
	return 'WIN' if r else 'LOSE'
T = int(input())
for _ in range(T):
	N = int(input())
	S = input()
	print(solve(S))


a = [0, 1, 2]
for n in range(3, 301):
	s = set()
	mid = n // 2
	for i in range(mid + 1):
		s.add(a[i] ^ a[n - 1 - i])
	if n % 2 == 0:
		mid = n // 2 - 1
	for i in range(mid + 1):
		s.add(a[i] ^ a[n - 2 - i])
	m = 0
	while m in s:
		m = m + 1
	a.append(m)
n = int(input())
for i in range(n):
	input()
	s = input().split('X')
	sum = 0
	for l in range(len(s)):
		sum ^= a[len(s[l])]
	if sum == 0:
		print('LOSE')
	else:
		print('WIN')


import os
import sys
win = [0]
for n in range(1, 301):
	s = set()
	for a in range(n // 2 + 1):
		s.add(win[a] ^ win[n - 1 - a])
		s.add(win[a] ^ win[n - 2 - a])
	m = 0
	while m in s:
		m += 1
	win.append(m)

def solve(S):
	r = 0
	for s in S.split('X'):
		r ^= win[len(s)]
	if r:
		return 'WIN'
	else:
		return 'LOSE'
T = int(input())
for _ in range(T):
	N = int(input())
	S = input()
	print(solve(S))


p = {0: 0, 1: 1, 2: 2, 3: 3}
for i in range(4, 301):
	s = set()
	for j in range(i - 1):
		s.add(p[j] ^ p[i - j - 1])
		s.add(p[j] ^ p[i - j - 2])
	gr = 0
	while gr in s:
		gr += 1
	p[i] = gr
t = int(input())
for ti in range(t):
	n = int(input())
	s = 'X' + input() + 'X'
	a = []
	L = 0
	for i in range(len(s)):
		if s[i] == 'X':
			if i != 0 and L != 0:
				a.append(L)
			L = 0
		else:
			L += 1
	gr = 0
	for i in a:
		gr ^= p[i]
	if gr == 0:
		print('LOSE')
	else:
		print('WIN')


p = {0: 0, 1: 1, 2: 2, 3: 3}
for i in range(4, 301):
	s = set()
	for j in range(i - 1):
		s.add(p[j] ^ p[i - j - 1])
		s.add(p[j] ^ p[i - j - 2])
	gr = 0
	while gr in s:
		gr += 1
	p[i] = gr
t = int(input())
for ti in range(t):
	n = int(input())
	s = 'X' + input() + 'X'
	a = []
	L = 0
	for i in range(len(s)):
		if s[i] == 'X':
			if i != 0 and L != 0:
				a.append(L)
			L = 0
		else:
			L += 1
	gr = 0
	for i in a:
		gr ^= p[i]
	if gr == 0:
		print('LOSE')
	else:
		print('WIN')


import os
import sys
grundy = [0]
for n in range(1, 301):
	mex_set = set()
	for i in range(n // 2 + 1):
		mex_set.add(grundy[i] ^ grundy[n - 1 - i])
		mex_set.add(grundy[i] ^ grundy[n - 2 - i])
	mex = 0
	while mex in mex_set:
		mex += 1
	grundy.append(mex)

def Declaring_Winner(pin):
	xor_value = 0
	for mex_set in pin.split('X'):
		xor_value ^= grundy[len(mex_set)]
	if xor_value == 0:
		return 'LOSE'
	else:
		return 'WIN'
t = int(input())
for x in range(t):
	n = int(input())
	pin = input()
	print(Declaring_Winner(pin))


import os
import sys

def isWinning(n, config):
	if __name__ == '__main__':
		fptr = open(os.environ['OUTPUT_PATH'], 'w')
		t = int(input())
		for t_itr in range(t):
			n = int(input())
			config = input()
			result = isWinning(n, config)
			fptr.write(result + '\n')
		fptr.close()
		import os
import sys
w = [0]
for num in range(1, 301):
	x = set()
	for y in range(num // 2 + 1):
		x.add(w[y] ^ w[num - 1 - y])
		x.add(w[y] ^ w[num - 2 - y])
	g = 0
	while g in x:
		g += 1
	w.append(g)

def game(x):
	returning = 0
	for x in input().strip().split('X'):
		returning ^= w[len(x)]
	if returning:
		return 'WIN'
	else:
		return 'LOSE'
for g in range(int(input().strip())):
	input()
	returning = 0
	for q in input().strip().split('X'):
		returning ^= w[len(q)]
	print('WIN' if returning else 'LOSE')


g = [0, 1, 2]
for n in range(3, 301):
	s = set()
	for l in (1, 2):
		for i in range((n - l) // 2 + 1):
			s.add(g[i] ^ g[n - l - i])
	m = 0
	while m in s:
		m += 1
	g.append(m)
for t in range(int(input().strip())):
	input()
	ret = 0
	for p in input().strip().split('X'):
		ret ^= g[len(p)]
	print('WIN' if ret else 'LOSE')


g = [0, 1, 2]
for n in range(3, 301):
	s = set()
	for l in (1, 2):
		for i in range((n - l) // 2 + 1):
			s.add(g[i] ^ g[n - l - i])
	m = 0
	while m in s:
		m += 1
	g.append(m)
for t in range(int(input().strip())):
	input()
	ret = 0
	for p in input().strip().split('X'):
		ret ^= g[len(p)]
	print('WIN' if ret else 'LOSE')


def game_from(board: str) -> list:
	game = []
	count = 0
	for c in board:
		if c == 'I':
			count += 1
		elif count > 0:
			game.append(count)
			count = 0
	if count > 0:
		game.append(count)
	return game

def moves_for(n: int, hits: [int]) -> [list]:
	moves = []
	for hit in hits:
		left = 0
		right = n - hit
		while left <= right:
			if left == 0 and right == 0:
				continue
			elif right < 1 <= left:
				moves.append([left])
			elif left < 1 <= right:
				moves.append([right])
			else:
				moves.append([left, right])
			left += 1
			right -= 1
	return moves

def mex_of(s: set) -> int:
	mex = 0
	while mex in s:
		mex += 1
	return mex

def g_of(n: int, cache: dict) -> int:
	if n < 3:
		return n
	else:
		result = cache.get(n, None)
		if result is not None:
			return result
		moves = moves_for(n, [1, 2])
		s = set()
		for move in moves:
			if len(move) == 1:
				s.add(g_of(move[0], cache))
			else:
				s.add(g_of(move[0], cache) ^ g_of(move[1], cache))
		result = mex_of(s)
		cache[n] = result
		return result

def winner(board: str, cache: dict) -> str:
	game = game_from(board)
	g = 0
	for i in game:
		g ^= g_of(i, cache)
	return 'WIN' if g != 0 else 'LOSE'
n = int(input().strip())
c = {}
for i in range(n):
	input()
	g = list(input().strip())
	print(winner(g, c))


def game_from(board: str) -> list:
	game = []
	count = 0
	for c in board:
		if c == 'I':
			count += 1
		elif count > 0:
			game.append(count)
			count = 0
	if count > 0:
		game.append(count)
	return game

def moves_for(n: int, hits: [int]) -> [list]:
	moves = []
	for hit in hits:
		left = 0
		right = n - hit
		while left <= right:
			if left == 0 and right == 0:
				continue
			elif right < 1 <= left:
				moves.append([left])
			elif left < 1 <= right:
				moves.append([right])
			else:
				moves.append([left, right])
			left += 1
			right -= 1
	return moves

def mex_of(s: set) -> int:
	mex = 0
	while mex in s:
		mex += 1
	return mex

def g_of(n: int, cache: dict) -> int:
	if n < 3:
		return n
	else:
		result = cache.get(n, None)
		if result is not None:
			return result
		moves = moves_for(n, [1, 2])
		s = set()
		for move in moves:
			if len(move) == 1:
				s.add(g_of(move[0], cache))
			else:
				s.add(g_of(move[0], cache) ^ g_of(move[1], cache))
		result = mex_of(s)
		cache[n] = result
		return result

def winner(board: str, cache: dict) -> str:
	game = game_from(board)
	g = 0
	for i in game:
		g ^= g_of(i, cache)
	return 'WIN' if g != 0 else 'LOSE'
n = int(input().strip())
c = {}
for i in range(n):
	input()
	g = list(input().strip())
	print(winner(g, c))


def game_from(board: str) -> list:
	game = []
	count = 0
	for c in board:
		if c == 'I':
			count += 1
		elif count > 0:
			game.append(count)
			count = 0
	if count > 0:
		game.append(count)
	return game

def moves_for(n: int, hits: [int]) -> [list]:
	moves = []
	for hit in hits:
		left = 0
		right = n - hit
		while left <= right:
			if left == 0 and right == 0:
				continue
			elif right < 1 <= left:
				moves.append([left])
			elif left < 1 <= right:
				moves.append([right])
			else:
				moves.append([left, right])
			left += 1
			right -= 1
	return moves

def mex_of(s: set) -> int:
	mex = 0
	while mex in s:
		mex += 1
	return mex

def g_of(n: int, cache: dict) -> int:
	if n < 3:
		return n
	else:
		result = cache.get(n, None)
		if result is not None:
			return result
		moves = moves_for(n, [1, 2])
		s = set()
		for move in moves:
			if len(move) == 1:
				s.add(g_of(move[0], cache))
			else:
				s.add(g_of(move[0], cache) ^ g_of(move[1], cache))
		result = mex_of(s)
		cache[n] = result
		return result

def winner(board: str, cache: dict) -> str:
	game = game_from(board)
	g = 0
	for i in game:
		g ^= g_of(i, cache)
	return 'WIN' if g != 0 else 'LOSE'
n = int(input().strip())
c = {}
for i in range(n):
	input()
	g = list(input().strip())
	print(winner(g, c))


import math
import os
import random
import re
import sys
g = [0, 1, 2]
for n in range(3, 301):
	s = set()
	for l in (1, 2):
		for i in range(int((n - l) / 2 + 1)):
			s.add(g[i] ^ g[n - l - i])
	m = 0
	while m in s:
		m += 1
	g.append(m)
for t in range(int(input().strip())):
	input()
	ret = 0
	for p in input().strip().split('X'):
		ret ^= g[len(p)]
	print('WIN' if ret else 'LOSE')


def game_from(board: str) -> list:
	game = []
	count = 0
	for c in board:
		if c == 'I':
			count += 1
		elif count > 0:
			game.append(count)
			count = 0
	if count > 0:
		game.append(count)
	return game

def moves_for(n: int, hits: [int]) -> [list]:
	moves = []
	for hit in hits:
		left = 0
		right = n - hit
		while left <= right:
			if left == 0 and right == 0:
				continue
			elif right < 1 <= left:
				moves.append([left])
			elif left < 1 <= right:
				moves.append([right])
			else:
				moves.append([left, right])
			left += 1
			right -= 1
	return moves

def mex_of(s: set) -> int:
	mex = 0
	while mex in s:
		mex += 1
	return mex

def g_of(n: int, cache: dict) -> int:
	if n < 3:
		return n
	else:
		result = cache.get(n, None)
		if result is not None:
			return result
		moves = moves_for(n, [1, 2])
		s = set()
		for move in moves:
			if len(move) == 1:
				s.add(g_of(move[0], cache))
			else:
				s.add(g_of(move[0], cache) ^ g_of(move[1], cache))
		result = mex_of(s)
		cache[n] = result
		return result

def winner(board: str, cache: dict) -> str:
	game = game_from(board)
	g = 0
	for i in game:
		g ^= g_of(i, cache)
	return 'WIN' if g != 0 else 'LOSE'
n = int(input().strip())
c = {}
for i in range(n):
	input()
	g = list(input().strip())
	print(winner(g, c))


import math
import os
import random
import re
import sys

def game_from(board: str) -> list:
	game = []
	count = 0
	for c in board:
		if c == 'I':
			count += 1
		elif count > 0:
			game.append(count)
			count = 0
	if count > 0:
		game.append(count)
	return game

def moves_for(n: int, hits: [int]) -> [list]:
	moves = []
	for hit in hits:
		left = 0
		right = n - hit
		while left <= right:
			if left == 0 and right == 0:
				continue
			elif right < 1 <= left:
				moves.append([left])
			elif left < 1 <= right:
				moves.append([right])
			else:
				moves.append([left, right])
			left += 1
			right -= 1
	return moves

def mex_of(s: set) -> int:
	mex = 0
	while mex in s:
		mex += 1
	return mex

def g_of(n: int, cache: dict) -> int:
	if n < 3:
		return n
	else:
		result = cache.get(n, None)
		if result is not None:
			return result
		moves = moves_for(n, [1, 2])
		s = set()
		for move in moves:
			if len(move) == 1:
				s.add(g_of(move[0], cache))
			else:
				s.add(g_of(move[0], cache) ^ g_of(move[1], cache))
		result = mex_of(s)
		cache[n] = result
		return result

def winner(board: str, cache: dict) -> str:
	game = game_from(board)
	g = 0
	for i in game:
		g ^= g_of(i, cache)
	return 'WIN' if g != 0 else 'LOSE'
n = int(input().strip())
c = {}
for i in range(n):
	input()
	g = list(input().strip())
	print(winner(g, c))


import math
import os
import random
import re
import sys

def game_from(board: str) -> list:
	game = []
	count = 0
	for c in board:
		if c == 'I':
			count += 1
		elif count > 0:
			game.append(count)
			count = 0
	if count > 0:
		game.append(count)
	return game

def moves_for(n: int, hits: [int]) -> [list]:
	moves = []
	for hit in hits:
		left = 0
		right = n - hit
		while left <= right:
			if left == 0 and right == 0:
				continue
			elif right < 1 <= left:
				moves.append([left])
			elif left < 1 <= right:
				moves.append([right])
			else:
				moves.append([left, right])
			left += 1
			right -= 1
	return moves

def mex_of(s: set) -> int:
	mex = 0
	while mex in s:
		mex += 1
	return mex

def g_of(n: int, cache: dict) -> int:
	if n < 3:
		return n
	else:
		result = cache.get(n, None)
		if result is not None:
			return result
		moves = moves_for(n, [1, 2])
		s = set()
		for move in moves:
			if len(move) == 1:
				s.add(g_of(move[0], cache))
			else:
				s.add(g_of(move[0], cache) ^ g_of(move[1], cache))
		result = mex_of(s)
		cache[n] = result
		return result

def winner(board: str, cache: dict) -> str:
	game = game_from(board)
	g = 0
	for i in game:
		g ^= g_of(i, cache)
	return 'WIN' if g != 0 else 'LOSE'
n = int(input().strip())
c = {}
for i in range(n):
	input()
	g = list(input().strip())
	print(winner(g, c))


import math
import os
import random
import re
import sys
g = [0, 1, 2]
for n in range(3, 301):
	s = set()
	for l in (1, 2):
		for i in range((n - l) // 2 + 1):
			s.add(g[i] ^ g[n - l - i])
	m = 0
	while m in s:
		m += 1
	g.append(m)
for t in range(int(input().strip())):
	input()
	ret = 0
	for p in input().strip().split('X'):
		ret ^= g[len(p)]
	if ret:
		print('WIN')
	else:
		print('LOSE')


def game_from(board: str) -> list:
	game = []
	count = 0
	for c in board:
		if c == 'I':
			count += 1
		elif count > 0:
			game.append(count)
			count = 0
	if count > 0:
		game.append(count)
	return game

def moves_for(n: int, hits: [int]) -> [list]:
	moves = []
	for hit in hits:
		left = 0
		right = n - hit
		while left <= right:
			if left == 0 and right == 0:
				continue
			elif right < 1 <= left:
				moves.append([left])
			elif left < 1 <= right:
				moves.append([right])
			else:
				moves.append([left, right])
			left += 1
			right -= 1
	return moves

def mex_of(s: set) -> int:
	mex = 0
	while mex in s:
		mex += 1
	return mex

def g_of(n: int, cache: dict) -> int:
	if n < 3:
		return n
	else:
		result = cache.get(n, None)
		if result is not None:
			return result
		moves = moves_for(n, [1, 2])
		s = set()
		for move in moves:
			if len(move) == 1:
				s.add(g_of(move[0], cache))
			else:
				s.add(g_of(move[0], cache) ^ g_of(move[1], cache))
		result = mex_of(s)
		cache[n] = result
		return result

def winner(board: str, cache: dict) -> str:
	game = game_from(board)
	g = 0
	for i in game:
		g ^= g_of(i, cache)
	return 'WIN' if g != 0 else 'LOSE'
n = int(input().strip())
c = {}
for i in range(n):
	input()
	g = list(input().strip())
	print(winner(g, c))