/** made by amunduzbaev **/
#include "grader.h"
#include <bits/stdc++.h>
#ifndef EVAL
#include "grader.cpp"
#endif
using namespace std;
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define ub upper_bound
#define lb lower_bound
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(),x.rend()
#define NeedForSpeed ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
//#define int long long
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef vector<int> vii;
typedef vector<pll> vpll;
typedef vector<pii> vpii;
template<class T> bool umin(T& a, const T& b) {return a > b? a = b, true:false;}
template<class T> bool umax(T& a, const T& b) {return a < b? a = b, true:false;}
const int NN = 1e3+5;
const int mod = 1e9+7;
const ll inf = 1e18;
const ld Pi = acos(-1);
#define MULTI 1
int n, m, k, ans, res, used[NN];
void solve(int n){
srand(time(NULL));
vii res;
if(n > 50){
for(int i=0;i<30;i++){
int in = rand()%n +1;
if(used[in]) {i--; continue;}
int val = kth(in);
int num = cnt(val);
if(num > n/3){
say_answer(val);
return;
}
}
} else {
if(n <= 2){
say_answer(kth(1));
return;
}
map<int, int> uu;
for(int i=1;i<=n;i++){
int in = i;
int val = kth(in);
if(uu.count(val)) continue;
uu[val] = 1;
int num = cnt(val);
if(num > n/3){
say_answer(val);
return;
}
}
}
say_answer(-1);
}
