#include "grader.h"
#include <iostream>
#include <vector>
#include <string>
#include <math.h>
#include <cmath>
#include <iomanip>
#include <cstdio>
#include <algorithm>
#include <numeric>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <deque>
#include <bitset>
#include <cstring>
#include <unordered_map>
using namespace std;
typedef long long ll;
void solve(int n){
srand(time(0));
vector<ll>d;
for(int i = 1; i <= n; i++){
d.push_back(i);
}
for(int step = 0; step < 30; step++){
ll x = rand() % d.size();
ll c = cnt(kth(d[x]));
if(c * 3 > n){
say_answer(kth(d[x]));
return;
}
swap(d[x], d[d.size() - 1]);
d.pop_back();
}
}
