Read problems statements in Mandarin Chinese, Russian and Vietnamese as well. 
Nim is a well-known combinatorial game, based on removing stones from piles. In this problem, we'll deal with a similar game, which we'll call Dual Nim. The rules of this game are as follows:

Initially, there are N piles of stones, numbered 1 through N. The i-th pile contains a_{i} stones.
The players take alternate turns. If the bitwise XOR of all piles equals 0 before a player's turn, then that player wins the game.
In his/her turn, a player must choose one of the remaining piles and remove it. (Note that if there are no piles, that player already won.)

Decide which player wins, given that both play optimally.

------ Input ------ 

The first line of the input contains an integer T - the number of test cases.
The first line of each test case contains N - the number of piles.
The following line contains N space-separated integers a_{1},..,a_{N} - the sizes of piles.

------ Output ------ 

For each test case, output one string on a separate line - "First" (without quotes) if the first player wins, "Second" (without quotes) if the second player wins.

------ Constraints ------ 

$1 ≤ T ≤ 10$
$1 ≤ N ≤ 500$
$1 ≤ a_{i} ≤ 500$

----- Sample Input 1 ------ 
3
4
1 2 4 8
3
2 3 3
5
3 3 3 3 3
----- Sample Output 1 ------ 
First
Second
Second

Difficulty: HARD
Tags: Bit manipulation

Constructive algorithms

Game theory

Mathematics

Ad-hoc
Skill types: Bit manipulation

Starter code:

Solutions:
from collections import *
from random import *
for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	d = defaultdict(int)
	for i in a:
		d[i] += 1
	b = []
	for (key, value) in d.items():
		if value % 2 == 1:
			b.append(key)
	count = 0
	for i in b:
		count = count ^ i
	if count == 0 or len(b) % 2 == 0:
		print('First')
	else:
		print('Second')


from functools import reduce
for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	b = [0] * 505
	for i in a:
		b[i] += 1
	a = []
	for (k, v) in enumerate(b):
		if v % 2 == 1:
			a.append(k)
	if len(a) % 2 == 0 or reduce(lambda x, y: y ^ x, a, 0) == 0:
		print('First')
	else:
		print('Second')


from collections import Counter
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	x = 0
	for i in a:
		x ^= i
	if x != 0:
		if n % 2:
			print('Second')
		else:
			print('First')
	else:
		print('First')


test = int(input())
for i in range(0, test):
	n = int(input())
	a = list(map(int, input().split()))
	ini_res = 0
	for j in a:
		ini_res = ini_res ^ j
	win = 'First'
	if ini_res != 0:
		if n % 2 != 0:
			win = 'Second'
	print(win)


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	value = 0
	for j in range(n):
		value = value ^ l[j]
	if value == 0:
		print('First')
	elif n % 2 == 0:
		print('First')
	else:
		print('Second')


T = int(input())
for t in range(T):
	n = int(input())
	A = list(map(int, input().split(' ')))
	res = 0
	for i in A:
		res ^= i
	print('First') if res == 0 else print('Second') if n & 1 else print('First')


import math
test = 1
test = int(input())
for tc in range(test):
	n = int(input())
	l = list(map(int, input().split()))
	val = 0
	for i in range(n):
		val = val ^ l[i]
	if val == 0:
		print('First')
	elif n % 2 == 0:
		print('First')
	else:
		print('Second')


from functools import reduce
problems = int(input())

def wincon(arr):
	if len(arr) == 0:
		return True
	return reduce(lambda x, y: x ^ y, arr) == 0
for _ in range(problems):
	counter = {}
	input()
	arr = list(map(int, input().split()))
	turn = 0
	while len(arr) >= 0:
		turn += 1
		if wincon(arr):
			break
		for i in range(len(arr)):
			new_arr = arr[0:i] + arr[i + 1:]
			if not wincon(new_arr):
				arr = new_arr.copy()
				break
		else:
			arr = arr[1:]
	if turn % 2 == 1:
		print('First')
	else:
		print('Second')


t = int(input())
for u in range(t):
	n = int(input())
	a = []
	x = 0
	s = input().split()
	for i in range(n):
		x = x ^ int(s[i])
	if x is 0:
		print('First')
	elif n % 2 is 0:
		print('First')
	else:
		print('Second')


for tc in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	val = 0
	for i in range(n):
		val = val ^ l[i]
	if val == 0:
		print('First')
	elif n % 2 == 0:
		print('First')
	else:
		print('Second')


for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	t = 0
	for i in range(n):
		t = t ^ a[i]
	if t == 0:
		print('First')
	elif n % 2 == 0:
		print('First')
	else:
		print('Second')


t = int(input())
for _ in range(t):
	n = int(input())
	num = list(map(int, input().split()))
	ans = 0
	for i in range(n):
		ans = ans ^ num[i]
	if ans == 0:
		print('First')
	else:
		for j in range(n + 1):
			count = 0
			for i in range(n):
				if num[i] != 0 and num[i] ^ ans != 0:
					count += 1
					ans = ans ^ num[i]
					num[i] = 0
					break
			if count == 0:
				if j % 2 == 0:
					print('Second')
					break
				else:
					print('First')
					break


for i in range(int(input())):
	n = int(input())
	s = 0
	a = [int(x) for x in input().split()]
	for j in range(n):
		s = s ^ a[j]
	if s == 0:
		print('First')
	elif n % 2 == 0:
		print('First')
	else:
		print('Second')


from functools import reduce
for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	print(['Second', 'First'][reduce(lambda x, y: x ^ y, l) == 0 or n % 2 == 0])


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	ans = 0
	for i in range(n):
		ans = ans ^ arr[i]
	isWinning = True
	if ans:
		if n % 2 == 1:
			isWinning = False
	print('First' if isWinning else 'Second')


n = int(input())
for j in range(n):
	m = int(input())
	l = list(map(int, input().split()))
	g = 0
	for i in l:
		g ^= i
	if g == 0:
		print('First')
	elif m % 2 == 0:
		print('First')
	else:
		print('Second')


for _ in range(int(input())):
	n = int(input())
	arr = [int(c) for c in input().split()]
	xor = 0
	for i in arr:
		xor ^= i
	if xor == 0:
		print('First')
	elif n & 1:
		print('Second')
	else:
		print('First')


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	s = a[0]
	for i in range(1, len(a)):
		s ^= a[i]
	if s == 0 or n % 2 == 0:
		print('First')
	else:
		print('Second')


from random import *
from collections import *
t = int(input())
for _ in range(t):
	n = int(input())
	arr = map(int, input().split())
	d = defaultdict(int)
	for a in arr:
		d[a] += 1
	arr = []
	for (k, v) in d.items():
		if v % 2 == 1:
			arr.append(k)
	xor = 0
	for a in arr:
		xor = a ^ xor
	if xor == 0 or len(arr) % 2 == 0:
		print('First')
	else:
		print('Second')


for t in range(int(input())):
	n = int(input())
	nums = [int(x) for x in input().split()]
	ans = 0
	for num in nums:
		ans = ans ^ num
	if ans == 0:
		print('First')
	elif n % 2 == 0:
		print('First')
	else:
		print('Second')


t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	x = 0
	for i in range(n):
		x = x ^ l[i]
	if x == 0:
		print('First')
	else:
		c = 1
		while 1:
			flag = 0
			for i in range(n):
				if x ^ l[i] == 0 or l[i] == 0:
					continue
				else:
					flag = 1
					x = x ^ l[i]
					l[i] = 0
					break
			c = (c + 1) % 2
			if flag == 0:
				break
		if c == 1:
			print('First')
		else:
			print('Second')


t = int(input())
for a0 in range(t):
	n = int(input())
	arr = list(map(int, input().split(' ')))
	t = 0
	for i in arr:
		t = t ^ i
	if t == 0:
		print('First')
	elif n % 2 == 0:
		print('First')
	else:
		print('Second')


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split(' ')))
	b = [0 for j in range(n)]
	xor = 0
	for j in range(n):
		xor ^= a[j]
	j = 0
	while True:
		if xor == 0:
			if j % 2 == 0:
				print('First')
			else:
				print('Second')
			break
		else:
			flag = True
			for k in range(n):
				if a[k] != xor and b[k] == 0:
					xor ^= a[k]
					b[k] = 1
					flag = False
					break
			if flag:
				xor = 0
		j += 1


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	xor = 0
	for i in a:
		xor ^= i
	if xor == 0:
		print('First')
	elif n % 2:
		print('Second')
	else:
		print('First')


s = int(input())
for i in range(s):
	t = int(input())
	l = list(map(int, input().split()))
	v = 0
	for j in range(t):
		v = v ^ l[j]
	if v == 0:
		print('First')
	elif t % 2 == 0:
		print('First')
	else:
		print('Second')


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	x = 0
	freq = [0] * 501
	for i in range(n):
		x ^= a[i]
		freq[a[i]] += 1
	if x == 0:
		print('First')
	else:
		ans = 1
		for i in range(1, 501):
			if freq[i] != 0:
				if freq[i] % 2 != 0:
					ans *= -1
		if ans == -1:
			print('Second')
		else:
			print('First')