Game on Plane

Time limit1sMemory limit1024 MB

Summary

Players alternately draw non-crossing segments between vertices of a regular N-gon, and the one who completes a convex polygon wins. Decide who should move first to force a win.

Level: Hard8 of 10
Topics: Game theory, Geometry
Solved: No attempts yet

Problem

You are given $N$ points on a plane. These points are exactly the vertices of a regular $N$ -gon. Koosaga, an extreme villain, challenges you to a game using these points. You and Koosaga take turns, and on each turn the player does the following.

Chooses two of the given points.
Draws the line segment connecting the two chosen points.

The newly drawn segment must not cross any previously drawn segment in its interior. Two segments may meet at their endpoints. If at any point a convex polygon formed by the drawn segments exists, the game ends, and the last player to move wins.

Koosaga lets you choose who moves first. Given the integer $N$ , decide whether you must move first or second so that you can win no matter how Koosaga plays.

Input

The input consists of many test cases. The first line contains an integer $T$ ( $1\leq T\leq 5,000$ ), the number of test cases. Each of the following $T$ lines contains one integer $N$ ( $3\leq N\leq 5,000$ ).

Output

For each test case, print one line containing First if you must move first, or Second if you must move second so that you can win no matter how Koosaga plays.

Examples1

Example 1
Input
```
2
3
5
```
Expected output
```
First
Second
```