Problem: Good job! Now that Heidi is able to distinguish between Poisson and uniform distributions, she is in a good position to actually estimate the populations.

Can you help Heidi estimate each village's population?

Input

Same as the easy version.

Output

Output one line per village, in the same order as provided in the input, containing your (integer) population estimate.

Your answer is considered correct if it is an integer that falls into the interval <image>, where P is the real population of the village, used to create the distribution (either Poisson or uniform) from which the marmots drew their answers.

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
#define ll long long
#define INF 1000000005
#define MOD 1000000007
#define EPS 1e-10
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define rrep(i,n) for(int i=(int)(n)-1;i>=0;--i)
#define srep(i,s,t) for(int i=(int)(s);i<(int)(t);++i)
#define each(a,b) for(const auto& (a): (b))
#define all(v) (v).begin(),(v).end()
#define len(v) (int)(v).size()
#define zip(v) sort(all(v)),v.erase(unique(all(v)),v.end())
#define cmx(x,y) x=max(x,y)
#define cmn(x,y) x=min(x,y)
#define fi first
#define se second
#define pb push_back
#define show(x) cout<<#x<<" = "<<(x)<<endl
#define sar(a,n) {cout<<#a<<":";rep(pachico,n)cout<<" "<<a[pachico];cout<<endl;}

using namespace std;

template<typename S,typename T>auto&operator<<(ostream&o,pair<S,T>p){return o<<"{"<<p.fi<<","<<p.se<<"}";}
template<typename T>auto&operator<<(ostream&o,set<T>s){for(auto&e:s)o<<e<<" ";return o;}
template<typename S,typename T,typename U>
auto&operator<<(ostream&o,priority_queue<S,T,U>q){while(!q.empty())o<<q.top()<<" ",q.pop();return o;}
template<typename K,typename T>auto&operator<<(ostream&o,map<K,T>&m){for(auto&e:m)o<<e<<" ";return o;}
template<typename T>auto&operator<<(ostream&o,vector<T>v){for(auto&e:v)o<<e<<" ";return o;}
void ashow(){cout<<endl;}template<typename T,typename...A>void ashow(T t,A...a){cout<<t<<" ";ashow(a...);}
template<typename S,typename T,typename U>
struct TRI{S fi;T se;U th;TRI(){}TRI(S f,T s,U t):fi(f),se(s),th(t){}
bool operator<(const TRI&_)const{return(fi==_.fi)?((se==_.se)?(th<_.th):(se<_.se)):(fi<_.fi);}};
template<typename S,typename T,typename U>
auto&operator<<(ostream&o,TRI<S,T,U>&t){return o<<"{"<<t.fi<<","<<t.se<<","<<t.th<<"}";}

typedef pair<int, int> P;
typedef pair<ll,ll> pll;
typedef TRI<int, int, int> tri;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<double> vd;
typedef vector<P> vp;
typedef vector<string> vs;

const int MAX_N = 100005;

int bue[MAX_N];
double sm[MAX_N], LOG[MAX_N];

double solve1(int k, int p){
    return k * LOG[p] - p - sm[k];
}

double solve2(int p){
    return -LOG[2*p+1];
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    rep(i,MAX_N){
        LOG[i] = log(i);
        if(i) sm[i] = sm[i-1] + LOG[i];
    }
    rep(i,n){
        double mean = 0;
        rep(j,250){
            cin >> bue[j];
            mean += bue[j];
        }
        mean /= 250.0;
        double hoge = 0;
        rep(j,250){
            hoge += (bue[j] - mean) * (bue[j] - mean);
        }
        hoge /= 250.0;
        if(abs(hoge - mean) < abs(hoge - mean * mean / 3.0)){
            int ans = -1;
            double res = -1e300;
            srep(p,10,1001){
                double ch = 0;
                rep(j,250){
                    ch += solve1(bue[j], p);
                }
                if(ch > res) res = ch, ans = p;
            }
            cout<< ans << "\n";
        }else{
            const int cand = (*max_element(bue, bue + 250) + 1) / 2;
            cout << cand << "\n";
            // if(cand < 50){
            // }else{
            //     const int ans = round(mean);
            //     cout << ans << "\n";
            // }
            // double res = -1e300;
            // srep(p,10,1001){
            //     double ch = 0;
            //     rep(j,250){
            //         ch += solve2(p);
            //     }
            //     if(ch > res) ch = res, ans = p;
            // }
        }
    }
    return 0;
}