#include<bits/stdc++.h>
#include "puzzle.h"
#define LL int
#define SZ(x) ((LL)(x.size()))
#define all(x) (x).begin(),(x).end()
using namespace std;
/*inline LL read(){
  LL q=0,w=1;char ch=getchar();
  while(ch>'9' || ch<'0'){if(ch=='-')w=-1;ch=getchar();}
  while(ch>='0'&&ch<='9'){q=q*10+(ch-'0');ch=getchar();}
  return q*w;
}
void write(LL x){
  if(x<0){putchar('-');x=(-x);}
  if(x>9)write(x/10);
  putchar('0'+x%10);
}
inline void writeln(LL x){write(x);puts("");}
inline void writecs(LL x){write(x);putchar(' ');}*/

inline void dmin(LL &x,LL y){if(x>y)x=y;return ;}
inline void dmax(LL &x,LL y){if(x<y)x=y;return ;}

#define cout cerr
#define pb push_back

namespace GenHelper{
#define ull unsigned long long
  ull seed=19260817ull;
  inline void Get(){seed^=(seed<<7);seed^=(seed>>11);seed^=(seed<<13);}
  inline ull Rand(){Get();return (seed^(seed<<32ull));}
}using GenHelper::Rand;
inline LL random(LL l,LL r){return (Rand()%(r-l+1)+l);}

const LL N = 1000+95 ;
bitset<N>ok[N];LL a[N];
void play(LL n){
  LL SUM=n*(n-1);
  for(LL x=0;x<n;x++){a[x]=n;for(LL i=0;i<n;i++)ok[x][i]=1;}
  LL _TC_=0;
  while(true){
    _TC_++;
    vector<LL>p(n);
    for(LL i=0;i<n;i++)p[i]=i;
    for(LL i=0;i<n;i++)swap(p[i],p[random(0,(n-1))]);

    LL fl=0;
    for(LL i=0;i<n;i++)if(ok[i][p[i]]){fl++;}
    if(!fl)continue;
    //    cerr<<" fl = "<<fl<<" SUM = "<<SUM<<" n = "<<n<<endl;
    if(fl<=(LL)(1.0*min(SUM,n)/sqrt(_TC_)))continue;
    
    LL cnt=query(p);
    if(!cnt){for(LL i=0;i<n;i++){a[i]-=ok[i][p[i]];SUM-=ok[i][p[i]];ok[i][p[i]]=0;}}
    LL TC=0;
    for(LL i=0;i<n;i++)TC+=((a[i]==1)?(1):(0));
    if(TC==n)break;
  }
  vector<LL>p;
  for(LL i=0;i<n;i++)
    for(LL j=0;j<n;j++)if(ok[i][j])p.pb(j);
  check(p);return ;
}