F - Game on Plane （ SG博弈 ）

F - Game on Plane （ sg博弈 ）

推荐阅读：https://blog.csdn.net/strangedbly/article/details/51137432

You are given NN points on a plane. These points are precisely the set of vertices of some regular NN-gon. Koosaga, an extreme villain, is challenging you with a game using these points. You and Koosaga alternatively take turns, and in each turn, the player

1. chooses two of the given points, then
2. draws the line segment connecting the two chosen points.

Also, the newly drawn line segment must not intersect with any of the previously drawn line segments in the interior. It is possible for two segments to meet at their endpoints. If at any point of the game, there exists a convex polygon consisting of the drawn line segments, the game ends and the last player who made the move wins.

Given the integer NN, Koosaga is letting you decide who will move first. Your task is decide whether you need to move first or the second so that you can win regardless of Koosaga's moves.

Input

The input consists of many test cases. The first line contains an integer TT (1≤T≤50001≤T≤5000), the number of test cases. Each of the following TT test cases is consisted of one line containing the integer NN (3≤N≤50003≤N≤5000).

Output

For each test case, print one line containing the string First if you need to move first or Second if you need to move second so that you can win regardless of Koosaga's moves.

Example

Input

2
3
5

Output

First
Second

 

题意：有n个点，两个人进行游戏，每一次move是连接任意两个点，游戏过程中不能有交叉，当一个人没有点可以连时他就输了。

思路：sg博弈，n=5的子情况有（0，3）（1，2）这一点需要明确，因为子情况是分为两部分的所以需要取一个异或值。

 

代码：

#include<bits/stdc++.h>

using namespace std;

int sg[5005];
int via[5005];

void getsg()
{
    memset(sg,0,sizeof(sg));
    sg[0] = sg[1] = 0;
    sg[2] = 1;
    for ( int i=3; i<=5002; i++ ) {
        memset(via,0,sizeof(via));
        int t = i-2;
        for ( int j=0; j<=t/2; j++ ) {
            via[ sg[j]^sg[t-j] ] = 1;
        }
        for ( int j=0; j<=5002; j++ ) {
            if ( via[j]==0 ) {
                sg[i] = j;
                break ;
            }
        }
    }
}

int main()
{
    getsg();
    int n,listt;
    cin >> listt;
    while ( listt-- ) {
        cin >> n;
        if ( sg[n]==0 ) {
            cout << "Second" << endl;
        }
        else {
            cout << "First" << endl;
        }
    }

    return 0;
}