\documentclass{article}
\usepackage{graphicx} % Required for inserting images

\title{test}
\author{z1284537530 }
\date{March 2023}

\begin{document}

\maketitle

After their success in coming up with Fun Game, Kyle and Mike invented another game having the following rules:

The game starts with an $n$-element sequence, $*2^1*2^2*2^3*\ldots*2^n$, and is played by two players, $\mathbf{P_1}$ and $P_2$. 
The players move in alternating turns, with $\mathbf{P_1}$ always moving first. During each move, the current player chooses one of the asterisks ($\lt\:k$) in the above sequence and changes it to either a + (plus) or a - (minus) sign.  
The game ends when there are no more asterisks ($\lt\:k$) in the expression. If the evaluated value of the sequence is divisible by $17$, then $P_2$ wins; otherwise, $\mathbf{P_1}$ wins.

Given the value of $n$, can you determine the outcome of the game? Print $\textbf{First}$ if $\mathbf{P_1}$ will win, or $\textbf{Second}$ if $P_2$ will win. Assume both players always move optimally.

Input Format

The first line of input contains a single integer $\mathbf{T}$, denoting the number of test cases.
Each line $\boldsymbol{i}$ of the $\mathbf{T}$ subsequent lines contains an integer, $n$, denoting the maximum exponent in the game's initial sequence.

Constraints

$1\leq T\leq10^6$
$1\leq n\leq10^{6}$

Output Format

For each test case, print either of the following predicted outcomes of the game on a new line:

Print $\textbf{First}$ if $\mathbf{P_1}$ will win.
Print $\textbf{Second}$ if $P_2$ will win.

Sample Input
1
2  

Sample Output
First

Explanation

In this case, it doesn't matter in which order the asterisks are chosen and altered. There are $\begin{array}{c}4\end{array}$ different courses of action and, in each one, the final value is not divisible by $17$ (so $P_2$ always loses and we print $\textbf{First}$ on a new line). 

Possible options:

$+2^1+2^2=6$
$+2^1-2^2=-2$
$-2^1+2^2=2$
$-2^1-2^2=-6$


\section{Introduction}

\end{document}

Difficulty: MEDIUM
Tags: Game theory

Starter code:

Solutions:
r = ['First', 'Second']
for i in range(int(input())):
	print(r[not int(input()) % 8])


cases = int(input())
for _ in range(cases):
	n = int(input())
	if n % 8:
		print('First')
	else:
		print('Second')


import sys
t = int(input().strip())
for a0 in range(t):
	x = int(input())
	if x % 8:
		print('First')
	else:
		print('Second')


var = int(input())
for i in range(1, var + 1):
	k = int(input())
	if k % 8 == 0:
		print('Second')
	else:
		print('First')


T = int(input())
for _ in range(T):
	N = int(input())
	if N % 8 == 0:
		print('Second')
	else:
		print('First')


[print('First' if int(input()) % 8 else 'Second') for _ in range(int(input()))]


for _ in range(int(input())):
	print('Second' if int(input()) % 8 == 0 else 'First')


[print('First' if int(input()) % 8 else 'Second') for _ in range(int(input()))]


[print('First' if int(input()) % 8 else 'Second') for _ in range(int(input()))]


[print('First' if int(input()) % 8 else 'Second') for _ in range(int(input()))]


[print('First' if int(input()) % 8 else 'Second') for _ in range(int(input()))]


def calculate(n):
	return n % 8 == 0
t = int(input())
for i in range(t):
	print(['First', 'Second'][calculate(int(input()))])


[print('First' if int(input()) % 8 else 'Second') for _ in range(int(input()))]


[print('First' if int(input()) % 8 else 'Second') for _ in range(int(input()))]


for _ in range(int(input())):
	if int(input()) % 8:
		print('First')
	else:
		print('Second')


for i in range(int(input())):
	if int(input()) % 8:
		print('First')
	else:
		print('Second')


for _ in range(int(input())):
	if int(input()) % 8:
		print('First')
	else:
		print('Second')


[print('First' if int(input()) % 8 else 'Second') for _ in range(int(input()))]


[print('First' if int(input()) % 8 else 'Second') for _ in range(int(input()))]


t = int(input().strip())
for i in range(t):
	n = int(input().strip())
	if n % 8 == 0:
		print('Second')
	else:
		print('First')


[print('First' if int(input()) % 8 else 'Second') for _ in range(int(input()))]


[print('First' if int(input()) % 8 else 'Second') for _ in range(int(input()))]


for t in range(int(input())):
	print(['Second', 'First'][int(input()) % 8 > 0])


[print('First' if int(input()) % 8 else 'Second') for _ in range(int(input()))]


[print('First' if int(input()) % 8 else 'Second') for _ in range(int(input()))]


[print('SFeicrosntd'[int(input()) % 8 > 0::2]) for _ in 'x' * int(input())]


t = int(input())
for _ in range(t):
	n = int(input())
	if n % 8 == 0:
		print('Second')
	else:
		print('First')


import sys
T = int(sys.stdin.readline())
for i in range(0, T):
	n = int(sys.stdin.readline())
	if n % 8 == 0:
		print('Second')
	else:
		print('First')


[print('First' if int(input()) % 8 else 'Second') for _ in range(int(input()))]


print(*('First' if int(input()) & 7 else 'Second' for _ in range(int(input()))), sep='\n')


import sys
T = int(input().strip())
for a0 in range(T):
	n = int(input().strip())
	if n % 8 == 0:
		print('Second')
	else:
		print('First')


for _ in range(int(input())):
	print('First' if int(input()) % 8 else 'Second')


T = int(input().strip())
for a0 in range(T):
	n = int(input().strip())
	if n % 8 == 0:
		print('Second')
	else:
		print('First')


[print('First' if int(input()) % 8 else 'Second') for _ in range(int(input()))]


for _ in range(int(input())):
	if int(input()) % 8:
		print('First')
	else:
		print('Second')


for _ in range(int(input())):
	if int(input()) % 8:
		print('First')
	else:
		print('Second')


cases = int(input())
for _ in range(cases):
	max_exponent = int(input())
	if max_exponent % 8 == 0:
		print('Second')
	else:
		print('First')


[print('First' if int(input()) % 8 else 'Second') for _ in range(int(input()))]


T = int(input())
for t in range(0, T):
	n = int(input())
	if n % 8 == 0:
		print('Second')
	else:
		print('First')


for i in range(int(input())):
	if int(input()) % 8 == 0:
		print('Second')
	else:
		print('First')


import sys
test_count = int(input().strip())
for _ in range(test_count):
	power_range = int(input().strip())
	print('Second' if power_range % 8 == 0 else 'First')


t = int(input())
for l in range(t):
	n = int(input())
	if n % 8:
		print('First')
	else:
		print('Second')


T = int(input())
for i in range(T):
	n = int(input())
	if n % 8:
		print('First')
	else:
		print('Second')


t = int(input())
for i in range(t):
	n = int(input())
	if n % 8 == 0:
		print('Second')
	else:
		print('First')


for _ in range(int(input())):
	print('Second' if int(input()) % 8 == 0 else 'First')


[print('First' if int(input()) % 8 else 'Second') for _ in range(int(input()))]


for _ in range(int(input())):
	print('First' if int(input()) & 7 else 'Second')


for _ in range(int(input())):
	print('First' if int(input()) % 8 else 'Second')


t = int(input())
for ti in range(t):
	n = int(input())
	if n % 8 == 0:
		print('Second')
	else:
		print('First')


[print('First' if int(input()) % 8 else 'Second') for _ in range(int(input()))]


t = int(input().strip())
for i in range(t):
	if int(input().strip()) % 8:
		print('First')
	else:
		print('Second')


a = int(input())
for i in range(a):
	if int(input()) % 8:
		print('First')
	else:
		print('Second')


[print('First' if int(input()) % 8 else 'Second') for _ in range(int(input()))]


[print('First' if int(input()) % 8 else 'Second') for _ in range(int(input()))]


for i in range(int(input())):
	n = int(input())
	if n % 8 == 0:
		print('Second')
	else:
		print('First')


[print('First' if int(input()) % 8 else 'Second') for _ in range(int(input()))]


T = int(input().strip())
for _ in range(T):
	n = int(input().strip())
	print('Second' if n % 8 == 0 else 'First')


[print('First' if int(input()) % 8 else 'Second') for _ in range(int(input()))]


[print('First' if int(input()) % 8 else 'Second') for _ in range(int(input()))]


for i in range(int(input())):
	print('First' if int(input()) % 8 else 'Second')


for i in range(int(input())):
	if int(input()) % 8 == 0:
		print('Second')
	else:
		print('First')


import sys
for _ in range(int(input())):
	if int(input()) % 8:
		print('First')
	else:
		print('Second')


[print('First' if int(input()) % 8 else 'Second') for _ in range(int(input()))]


import random

def find_winner(n):
	num = 2
	sum = 0
	for i in range(n):
		if random.randint(1, 2) == 1:
			sum += num
		else:
			sum -= num
		num = num * 2
	if sum % 17 == 0:
		return 'Second'
	return 'First'
T = int(input().strip())
for i in range(T):
	n = int(input().strip())
	if n % 8 == 0:
		print('Second')
	else:
		print('First')


import sys
data = sys.stdin.readlines()
num_tests = data.pop(0)
for test in data:
	if int(test) % 8:
		print('First')
	else:
		print('Second')


for a in range(int(input())):
	if int(input()) % 8 != 0:
		print('First')
	else:
		print('Second')


import sys
t = int(input())
for _ in range(t):
	n = int(input())
	if n % 8 == 0:
		print('Second')
	else:
		print('First')


[print('First' if int(input()) % 8 else 'Second') for _ in range(int(input()))]


[print('First' if int(input()) % 8 else 'Second') for _ in range(int(input()))]


def parseInput(f):
	return [f(x) for x in input().split()]
t = int(input())
for _ in range(t):
	n = int(input())
	print('First' if n % 8 else 'Second')


[print('First' if int(input()) % 8 else 'Second') for _ in range(int(input()))]


[print('First' if int(input()) % 8 else 'Second') for _ in range(int(input()))]


t = int(input().strip())
for i in range(t):
	n = int(input().strip())
	print('First' if n % 8 > 0 else 'Second')


def whowins(n):
	if n % 8 == 0:
		return 'Second'
	else:
		return 'First'
g = int(input().strip())
for a0 in range(g):
	n = int(input().strip())
	print(whowins(n))


for _ in range(int(input())):
	n = int(input())
	print('First' if n & 7 else 'Second')


import os
import sys

def powersGame(n):
	if n % 8 == 0:
		print('Second')
	else:
		print('First')
t = int(input())
for t_itr in range(t):
	n = int(input())
	result = powersGame(n)


for i in range(int(input().strip())):
	print('First' if int(input()) % 8 else 'Second')


import os
import sys

def powersGame(n):
	for _ in range():
		if input() % 8:
			print('First')
		else:
			print('Second')
for _ in range(int(input())):
	if int(input()) % 8:
		print('First')
	else:
		print('Second')


import sys
from time import time

def solve(n):
	return n % 8 != 0
tm = time()
t = int(input())
for _ in range(t):
	n = int(input())
	if solve(n):
		print('First')
	else:
		print('Second')
print('time elapsed: %s' % (time() - tm,), file=sys.stderr)


import os
import sys
[print('First' if int(input()) % 8 else 'Second') for _ in range(int(input()))]


import os
import sys
a = int(input())
for _ in range(a):
	b = int(input())
	if b % 8:
		print('First')
	else:
		print('Second')


[print('First' if int(input()) % 8 else 'Second') for _ in range(int(input()))]


for _ in range(int(input())):
	print('First' if int(input()) % 8 else 'Second')


for _ in range(int(input())):
	print('First' if int(input()) % 8 else 'Second')