Dual Nim | CodeChef

Dual Nim

Problem code: TWONIM

All submissions for this problem are available.

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 ai 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 a1,..,aN - 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 ≤ ai ≤ 500

Example

Input:
3
4
1 2 4 8
3
2 3 3
5
3 3 3 3 3

Output:
First
Second
Second
Author: 7★xellos0
Tester: 6★antoniuk1
Editorial http://discuss.codechef.com/problems/TWONIM
Tags cook68, easy, game-theory, nim, parity-obsv, xellos0
Date Added: 27-01-2016
Time Limit: 2 sec
Source Limit: 50000 Bytes
Languages: C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS


Comments

  • Please login at the top to post a comment.

SUCCESSFUL SUBMISSIONS


Fetching successful submissions