Shared code

#include <bits/stdc++.h>

#define int long long
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;

const int N = 1e6+5;
int dp[N];

int mex(vector<int> v){
    set<int> s;
    for(int i = 0;i < v.size();i++) s.insert(v[i]);
    for(int i = 0;i < N;i++) if(s.find(i)==s.end()) return i;
}

void init(){
    for(int i = 3;i <= 2000;i++){
        vector<int> v;
        for(int j = 1;j < (i+1)/2;j++){
            v.push_back(dp[j]^dp[i-j]);
        }
        dp[i] = mex(v);
    }
}

void solve(){
    int n;
    cin >> n;
    if(n > 2000) dp[n] = 1;
    cout << (dp[n] ? "first" : "second") << "\n";
}

signed main(){
    fastio
    init();
    int t = 1;
    cin >> t;
    while(t--) solve();
}