////COLECTIE REZ PE BITI
//#include <iostream>
//#include <fstream>
//#include <algorithm>
//using namespace std;
//ifstream fi("colectie.in");
//ofstream fo("colectie.out");
////ifstream fi("intrare.in");
////ofstream fo("iesire.out");
//int n,a[9001],i,j,k;
//void sortare (int n,int k[],int st,int dr){
// int i,j,a;
// i=st;
// j=dr;
// a=k[i];
// do{
// while(k[j]>=a and i<j)
// j=j-1;
// k[i]=k[j];
// while(k[i]<=a and i<j)
// i=i+1;
// k[j]=k[i];
// }while(i!=j);
// k[i]=a;
// if(st<i-1)
// sortare(n,k,st,i-1);
// if(i+1<dr)
// sortare(n,k,i+1,dr);
//}
//int main()
//{
// fi>>n;
// for(i=1;i<=n;i++)
// fi>>a[i];
// sortare(n,a,1,n);
// for(i=1;i<=n;i++)
// if(i==1)
// {if(a[i]!=a[i+1])
// k++;}
// else
// if(i==n)
// {if(a[i]!=a[i-1])
// k++;}
// else
// if(a[i]!=a[i-1] and a[i]!=a[i+1])
// k++;
// fo<<k;
// return 0;
//}
////Pachete
//#include <iostream>
//#include <fstream>
//#include <algorithm>
//using namespace std;
////ifstream fi("intrare.in");
////ofstream fo("iesire.out");
//ifstream fi("pachete.in");
//ofstream fo("pachete.out");
//int n,a[9001],i,j,k,pozlib,elem,b[100000];
//int cautapozlib(int a[],int n){
// int j;
// for(j=1;j<=n+1;j++)
// if(a[j]==0)
// return j;
//}
//int cautaelem(int a[],int n,int x){
// int j;
// for(j=1;j<=n+1;j++)
// if(a[j]==x)
// return j;
//}
//int main()
//{
// int st,dr,s=0;
// fi>>n;
// for(i=1;i<=n;i++)
// fi>>a[i];
// a[n+1]=0;
// k=1;
// for (i=1;i<=n;i++)
// if(a[i]!=i)
// { pozlib=cautapozlib(a,n);
// elem=cautaelem(a,n,i);
// if(a[i]!=a[pozlib])
// {
// swap(a[i],a[pozlib]);
// b[k++]=i;
// b[k++]=pozlib;
// }
// if(a[i]!=a[elem])
// {swap(a[i],a[elem]);
// b[k++]=elem;
// b[k++]=i;
// }
// }
// fo<<k/2<<endl;
// for(i=1;i<k;i+=2)
// fo<<b[i]<<" "<<b[i+1]<<endl;
//}
////prim001 RASPUNS GRESIT
//#include <iostream>
//#include <fstream>
//#include <algorithm>
//using namespace std;
//ifstream fi("intrare.in");
//ofstream fo("iesire.out");
//long long n,i,x,nr=1,d,k,aux,p;
//bool gata=0;
//int main()
//{
// cin>>n;
// aux=n;
// k=59999;
// d=2;
// while(n>1 && gata==0)
// {
// p=0;
// while(n%d==0)
// {p++;
// n=n/d;
// }
// if(p)
// {
// //fo<<d<<" "<<p<<endl;
// nr=(nr*(p*aux+1))%k;
// }
// d++;
// if(d*d>n and n>1)
// gata=1;
// }
// //fo<<endl;
// if(n>1)
// {
// //fo<<n<<" "<<p;
// nr=(nr*(aux+1))%k;
// cout<<nr+1;
// }
// else
// cout<<nr;
//}
//#include <iostream>
//#include <fstream>
//using namespace std;
//ifstream fi("prodmax.in");
//ofstream fo("prodmax.out");
////ifstream fi("serbare.in");
////ofstream fo("serbare.out");
//int n,a[1000][1000],fr[100][100],m,i,j,maxi;
//int main(){
// fi>>n>>m;
// for(i=1;i<=n;i++)
// for(j=1;j<=m;j++)
// fi>>a[i][j];
// for(i=1;i<=m;i++)
// {for(j=1;j<=n;j++)
// fr[i][a[j][i]]++;
// if(fr[i][2]>maxi and fr[i][0]==0)
// maxi=fr[i][2];
// }
// for(i=1;i<=m;i++)
// if(fr[i][0]==0 and fr[i][2]==maxi)
// fo<<i<<" ";
//}
//VARIANTA 33 SUBIECTUL 3 PROBLEMA 4
//#include <iostream>
//#include <fstream>
//using namespace std;
//ifstream fi("intrare.in");
//ofstream fo("iesire.out");
//int n,x,y,m,i,j,maxi,nr,dif,mini=1000,k;
//int main(){
// fi>>n;
// for(i=1;i<=n;i++)
// for(j=1;j<=n;j++)
// {fi>>x;
// if(x>99 and x<1000 and x>maxi)
// {maxi=x; k=0;}
// if(x==maxi)
// k++;
// }
// fi.close();
// ifstream fi("intrare.in");
// fi>>n;
// for(i=1;i<=n;i++)
// for(j=1;j<=n;j++)
// { fi>>y;
// dif=maxi-y;
// if(dif<0)
// dif=dif*(-1);
// if(dif!=0 or k!=1)
// if(dif<mini)
// {
// mini=dif;
// nr=y;
// }
// }
// fo<<maxi<<" "<<nr;
//}
////VARIANTA 34 SUBIECTUL 3 PROBLEMA 3
//#include <iostream>
//#include <fstream>
//using namespace std;
//ifstream fi("intrare.in");
//ofstream fo("iesire.out");
//int n,x[1000],m,i,j,nr,ok,dif,maxim,k;
//int maxi(int x[],int n){
// int st=1,dr=n;
// if(x[st]>x[dr])
// return x[st];
// else
// return x[dr];
//}
//int main(){
// fi>>n;
// for(i=1;i<=n;i++)
// { for(j=1;j<=n;j++)
// fi>>x[j];
// ok=1;
// if(x[1]<x[n])
// {for(j=2;j<=n;j++)
// if(maxi(x,j)!=x[j])
// ok=0;
// if(maxim<x[n] and ok==1)
// maxim=x[n];
// }
// else
// {for(j=2;j<=n;j++)
// if(maxi(x,j)!=x[1])
// ok=0;
// if(maxim<x[1] and ok==1)
// maxim=x[1];
// }
// }
// fo<<maxim;
//}
////VARIANTA 30 SUBIECTUL 3 PROBLEMA 4
//#include <iostream>
//#include <fstream>
//using namespace std;
//ifstream fi("intrare.in");
//ofstream fo("iesire.out");
//int n,i,st,dr,aux;
//float x;
//int maxi(int x[],int n){
// int st=1,dr=n;
// if(x[st]>x[dr])
// return x[st];
// else
// return x[dr];
//}
//int main(){
// fi>>n;
// for(i=1;i<=n;i++)
// {
// fi>>x;
// if(x>dr)
// {
// st=x;
// dr=x+1;
// fo<<st<<" "<<dr<<endl;
// }
// }
//}
////VARIANTA 35 SUBIECTUL 3 PROBLEMA 4
//#include <iostream>
//#include <fstream>
//using namespace std;
//ifstream fi("intrare.in");
//ofstream fo("iesire.out");
//int n,i,st,dr,aux,x,a[100],k,j;
//int sum(int x){
// int s=0,i;
// for(i=2;i<x;i++)
// if(x%i==0)
// s+=i;
// return s;
//}
//int main(){
// fi>>n;
// for(i=1;i<=n;i++)
// {
// fi>>x;
// a[sum(x)]++;
// }
// for(i=0;i<=37;i++)
// if(a[i])
// for(j=1;j<=a[i];j++)
// fo<<i<<" ";
//}
////VARIANTA 40 SUBIECTUL 3 PROBLEMA 4
//#include <iostream>
//#include <fstream>
//using namespace std;
//ifstream fi("intrare.in");
//ofstream fo("iesire.out");
//int n,i,st,dr,aux,x,a[100],k,j;
//int pr(int x){
// int i;
// if(x==1)
// return 0;
// for(i=2;i*i<=x;i++)
// if(x%i==0)
// return 0;
// return 1;
//}
//int sdiv(int y){
// int i,s=0;
// for(i=1;i<=y;i++)
// if(y%i==0)
// s+=i;
// return s;
//}
//int main(){
// fi>>n;
// cout<<sdiv(4);
// for(i=1;i<=n;i++)
// if(pr(sdiv(i)))
// fo<<i<<" ";
//}
////Varianta 50,subiectul 3,problema 3
//#include <iostream>
//#include <fstream>
//using namespace std;
//ifstream fi("intrare.in");
//ofstream fo("iesire.out");
//ifstream fi("kminsum.in");
//ofstream fo("kminsum.out");
//long long n,m,cif,i,maxi,mini=10,n2,fr[1000],b,a,k,s,p1,p,x,y;
//int divxy(int x,int y){
// if(x%y==0)
// return 1;
// else
// return 0;
//}
//int main(){
// fi>>a>>b>>n;
// if(a>b)
// swap(a,b);
// for(i=a;i<=b;i++)
// if(n%i==0)
// fr[++k]=i;
// for(i=1;i<=k;i++)
// fo<<fr[i]<<" ";
//}
////Varianta 49,subiectul 3,problema 3
//#include <iostream>
//#include <fstream>
//using namespace std;
//ifstream fi("intrare.in");
//ofstream fo("iesire.out");
//ifstream fi("kminsum.in");
//ofstream fo("kminsum.out");
//long long n,m,cif,i,maxi,mini=10,n2,fr[1000],b,a,k,s,p1,p,x,y;
//int divxy(int x,int y){
// if(x%y==0)
// return 1;
// else
// return 0;
//}
//int main(){
// fi>>a>>b>>n;
// if(a>b)
// swap(a,b);
// for(i=a;i<=b;i++)
// if(i%n==0)
// fr[++k]=i;
// for(i=1;i<=k;i++)
// fo<<fr[i]<<" ";
//}
////Varianta 49,subiectul 3,problema 4
//#include <iostream>
//#include <fstream>
//using namespace std;
//ifstream fi("intrare.in");
//ofstream fo("iesire.out");
////ifstream fi("kminsum.in");
////ofstream fo("kminsum.out");
//int n,m,cif,i,maxi,mini=10,n2,fr[1000],b,a,k,s,p1,p,x,y;
//void cmax(int a,int &b){
// b=0;
// while(a){
// if(a%10>b)
// b=a%10;
// a/=10;
// }
//}
//int main(){
// while(fi>>x){
// cmax(x,k);
// if(k>maxi)
// maxi=k;
// }
// fo<<maxi;
//}
////Varianta 47,subiectul 3,problema 4
//#include <iostream>
//#include <fstream>
//using namespace std;
//ifstream fi("intrare.in");
//ofstream fo("iesire.out");
////ifstream fi("kminsum.in");
////ofstream fo("kminsum.out");
//int n,i,maxi,mini,a[1000],s;
//void cif(int nr,int &s){
// int cifa;
// s=0;
// while(nr){
// cifa=nr%10;
// s+=cifa;
// nr/=10;
// }
//}
//int main(){
// fi>>n;
// for(i=1;i<=n;i++)
// {
// fi>>a[i];
// cif(a[i],s);
// if(s>maxi)
// maxi=s;
// }
// for(i=1;i<=n;i++)
// {
// cif(a[i],s);
// if(s==maxi)
// fo<<a[i]<<" ";
// }
//}
//#include <iostream>
//#include <fstream>
//using namespace std;
//ifstream fi("intrare.in");
//ofstream fo("iesire.out");
////ifstream fi("sumsec.in");
////ofstream fo("sumsec.out");
//int d,n,p,gata,i,x,doi,cinci;
//long long s;
//int nr2(int x){
// int d;
// d=2;
// while(x%d==0)
// {
// p++;
// x=x/d;
// }
// return p;
//}
//int nr5(int x){
// int d;
// d=5;
// while(x%d==0)
// {
// p++;
// x=x/d;
// }
// return p;
//}
//int main(){
// fi>>n;
// for(i=1;i<=n;i++)
// {fi>>x;
// doi+=nr2(x);
// cinci+=nr5(x);
// }
// fo<<doi<<" "<<cinci;
// return 0;
//}
////Varianta 80 subiectul 3 problema 3
//#include <iostream>
//#include <fstream>
//using namespace std;
//ifstream fi("intrare.in");
//ofstream fo("iesire.out");
////ifstream fi("sumsec.in");
////ofstream fo("sumsec.out");
//int n,a[1000],i,x,maxi;
//int egale(int x)
//{
// int cif;
// cif=x%10;
// while (x){
// if(cif!=x%10)
// return 0;
// x=x/10;
// }
// return 1;
//}
//int main(){
// int ok=0;
// while(fi>>x){
// if(egale(x))
// {a[x]++; ok=1;}
// if(x>maxi)
// maxi=x;
// }
// if(ok)
// {for(i=0;i<=maxi;i++)
// if(a[i]>=1)
// fo<<i<<" ";}
// else
// fo<<"NU EXISTA";
//}
//#include <iostream>
//#include <fstream>
//using namespace std;
//ifstream fi("intrare.in");
//ofstream fo("iesire.out");
////ifstream fi("sumsec.in");
////ofstream fo("sumsec.out");
//void sterge(int a[],int &n,int st,int dr)
//{
// int i,aux;
// aux=n-(dr-st+1);
// for(i=dr+1;i<=n;i++)
// a[st++]=a[i];
// n=aux;
//}
//int main(){
// int n,a[100],i,st,dr;
// fi>>n>>st>>dr;
// for(i=1;i<=n;i++)
// fi>>a[i];
// sterge(a,n,st,dr);
// for(i=1;i<=n;i++)
// fo<<a[i]<<" ";
//}
//
//
//#include <iostream>
//#include <fstream>
//using namespace std;
//ifstream fi("intrare.in");
//ofstream fo("iesire.out");
////ifstream fi("sumsec.in");
////ofstream fo("sumsec.out");
//int * sumaMinMax(int a[],int n)
//{
// int i,maxi=a[1],mini=a[1],sol[2],s=0;
// int *p;
// for(i=0;i<n;i++)
// {
// s+=a[i];
// if(a[i]>maxi)
// maxi=a[i];
// if(a[i]<mini)
// mini=a[i];
// }
// sol[1]=s-maxi;
// sol[2]=s-mini;
// p=&sol[1];
// return p;
//}
//int main(){
// int n,a[100],i,st,dr;
// fi>>n;
// for(i=0;i<n;i++)
// fi>>a[i];
// int *t=sumaMinMax(a,n);
// fo<<t[1]<<" "<<t[2];
//}
////CAMPION PANGLICA
//#include <iostream>
//#include <fstream>
//#include <algorithm>
//using namespace std;
////ifstream fi("intrare.in");
////ofstream fo("iesire.out");
//ifstream fi("panglica.in");
//ofstream fo("panglica.out");
//int x,n,i,lungime[1000],inceput[1000],C,sfarsit[1000],maxi,sol;
//int main(){
// fi>>n>>C;
// for(i=1;i<=n;i++)
// {
// fi>>x;
// if(inceput[x]==0)
// inceput[x]=i;
// else
// {sfarsit[x]=i;
// lungime[x]=sfarsit[x]-inceput[x]+1;
// if(lungime[x]>maxi)
// {
// maxi=lungime[x];
// sol=x;
// }
// }
// }
// fo<<lungime[sol]<<endl<<sol<<endl<<inceput[sol]-1<<endl<<n-sfarsit[sol];
//// for(i=1;i<=3;i++)
//// fo<<i<<" "<<inceput[i]<<" "<<sfarsit[i]<<" "<<lungime[i]<<endl;
//}
////PRIM007
//#include <fstream>
//#include <iostream>
//using namespace std;
//ifstream fi("intrare.in");
//ofstream fo("iesire.out");
//int x,n,l,nr,p,i,j,fr[10001],prim[20000],maxi,aux;
//long long k=0;
//int main(){
// cin>>n; //citesc elementele
// for(i=1;i<=n;i++)
// {
// cin>>x;
// fr[x]++; //frecventa elementelor
// if(x>maxi) //pana unde merg
// maxi=x;
// }
// aux=maxi;
// prim[0]=1;
// prim[1]=1;
// for(int i=2;i<=20000;++i) //ciur,vector cu numere prime
// if (prim[i]==0)
// {
// for(int j=i*2;j<=20000;j+=i)
// prim[j]=1;
// }
// maxi=aux;
// if(fr[1]>=2)
// k+=fr[1]*(fr[1]-1)/2;
// if(fr[2]>0 and fr[0]>0)
// k+=fr[2]*fr[0];
// for(i=0;i<=maxi;i+=2)
// for(j=1;j<=maxi;j+=2)
// if(fr[i]>0 and fr[j]>0)
// if(prim[i+j]==0)
// k=k+fr[i]*fr[j];
// cout<<k;
//}
////PRIM013 @.@
//#include <iostream>
//#include <fstream>
//using namespace std;
//ifstream fi("prim013.in");
//ofstream fo("prim013.out");
//ifstream fi("intrare.in");
//ofstream fo("iesire.out");
//long long prim[100000],i,j,n,x,k,d,ok,p,fr[100000];
//int main(){
// prim[0]=1;
// prim[1]=1;
// for(int i=2;i<=10000;++i)
// if (prim[i]==0)
// for(int j=i*2;j<=10000;j+=i)
// prim[j]=1;
// for(i=2;i<=10000;i++)
// if(prim[i]==0)
// {for(j=i;j<=10000;j=j*i)
// {k++;
// if(prim[k+1]==0)
// fr[j]=1;
// }
// k=0;
// }
// fi>>n;
// for(i=1;i<=n;i++)
// {fi>>x;
// if(fr[x]==1)
// k++;
// }
// fo<<k;
//}
////secventa 11
//#include <fstream>
//#include <iostream>
//using namespace std;
////ifstream fi("cautaprim.in");
////ofstream fo("cautaprim.out");
//ifstream fi("intrare.in");
//ofstream fo("iesire.out");
//int fr[1000],k,n,i,prim[101],sol,x,bin[300000],st,maxi;
//bool ok=false;
//int unu(int x){
// while(x/2!=0){
// if(x%2==0)
// return 0;
// x=x/2;
// }
// return 1;
//}
//int main()
//{
// cin>>n;
// for(int i=1;i<=n;i++)
// {
// cin>>x;
// bin[i]=unu(x);
// if(bin[i]==1)
// ok=true;
// }
// if(ok==false)
// {fo<<0;
// return 0;}
// st=1;
// while(st<=n)
// {
// if(bin[st]==1)
// while(bin[st]==1)
// {
// k++;
// st++;
// }
// else
// st++;
// if(k>maxi)
// maxi=k;
// k=0;
// }
// cout<<maxi;
//}
//#include <fstream>
//#include <iostream>
//using namespace std;
//ifstream fi("cautaprim.in");
//ofstream fo("cautaprim.out");
//ifstream fi("intrare.in");
//ofstream fo("iesire.out");
//long long n,i,x[1900900],p;
//bool ok=false;
//long long s;
//typedef long long NrMare[101000];
//void prod(NrMare x, int n)
//{
// long long i,t=0;
// for(i=1;i<=x[0];i++,t/=10)
// {
// t+=x[i]*n;
// x[i]=t%10;
// }
// for(;t;t/=10)
// x[++x[0]]=t%10;
//}
//void atrib(NrMare x, int n)
//{
// x[0]=0;
// if(n==0)
// x[(x[0]=1)]=0;
// else
// for(;n;n/=10)
// x[++x[0]]=n%10;
//}
//int main()
//{
// cin>>n;
// atrib(x,1);
// if(n%2==0)
// for(i=1;i<=n/2;i++)
// prod(x,4);
// else
// {
// for(i=1;i<=n/2;i++)
// prod(x,4);
// prod(x,2);
// }
// for(i=x[0];i>=1;i--)
// s+=x[i];
// cout<<s;
//}
//#include <fstream>
//#include <iostream>
//using namespace std;
//ifstream fi("intrare.in");
//ofstream fo("iesire.out");
//int n,m,a[10001],i,sol[1001],prim[1000];
//void citire(){
// cin>>n;
// for(i=1;i<=n;i++)
// cin>>a[i];
//}
//void afisare(int m,int sol[]){
// int i;
// if(m!=0)
// for(i=1;i<=1000;i++)
// {if(sol[i]==1)
// cout<<i<<" ";}
// else
// cout<<"Sirul Y este vid";
//}
//void genPrim(){
// int i,j;
// prim[0]=1;
// prim[1]=1;
// for(i=2;i<=1000;i++)
// if(prim[i]==0)
// for(j=2*i;j<=1000;j=j+i)
// prim[i]=1;
//}
//int desc(int x){
// int d=2,ok=1,p;
// while(x>1){
// p=0;
// while(x%d==0)
// {
// x/=d;
// p=p+1;
// }
// if(p==1)
// {
// sol[d]=1;
// m=1;
// }
// d++;
// }
//}
//int main()
//{
// m=0;
// citire();
// //genPrim();
// for(i=1;i<=n;i++)
// {
// desc(a[i]);
// }
// afisare(m,sol);
//}
//#include <fstream>
//#include <iostream>
//using namespace std;
//ifstream fi("intrare.in");
//ofstream fo("iesire.out");
//int n,m,i,sol,a[10000],fr[10000],k;
//void zero(int n,int a[]){
// int i,par[1000],impar[10000],stp=0,sti=0;
// for(i=1;i<=2*n;i++)
// if(a[i]%2==0)
// par[++stp]=a[i];
// else
// impar[++sti]=a[i];
// i=1;
// sti=1;
// stp=1;
// while(i<=2*n)
// {
// a[i+1]=par[stp++];
// a[i]=impar[sti++];
// i=i+2;
// }
//}
//int main()
//{
// fi>>n;
// for(i=1;i<=2*n;i++)
// fi>>a[i];
// zero(n,a);
// for(i=1;i<=2*n;i++)
// fo<<a[i]<<" ";
//}
//#include <fstream>
//#include <iostream>
//using namespace std;
//ifstream fi("intrare.in");
//ofstream fo("iesire.out");
//int sir(int x){
// int cif[100],k=0,i,ok=0;
// for(i=1;i<=11;i++)
// cif[i]=0;
// while(x)
// {
// cif[++k]=x%10;
// x=x/10;
// }
// while(k>1){
// if(cif[k]<cif[k-1])
// {k--;
// ok=1;
// }
// else
// if(cif[k]==cif[k-1])
// return 0;
// else
// {
// while(k>1)
// {
// if(cif[k]<cif[k-1] or ok==0)
// return 0;
// else
// if(cif[k]==cif[k-1])
// return 0;
// k--;
// }
// ok=2;
// }
// }
// if(ok==2)
// return 1;
// else
// return 0;
//}
//int main()
//{
// int n,a[10000],i,k,x,r;
// cin>>n;
// for(i=1;i<=n;i++)
// {
// cin>>x;
// a[i]=sir(x);
// }
// for(i=1;i<=n;i++)
// cout<<a[i]<<" "<<endl;
//}
//#include <fstream>
//#include <iostream>
//using namespace std;
//ifstream fi("intrare.in");
//ofstream fo("iesire.out");
//int main()
//{
// int n,a[10000],i,k,x,r;
// cin>>n>>k;
// if(n==1)
// {
// if(k!=0)
// cout<<k;
// else
// cout<<9;
// }
// else
// if(k==0)
// {
// cout<<1;
// for(i=2;i<n;i++)
// cout<<0;
// cout<<8;
// }
// else
// {
// cout<<1;
// for(i=2;i<n;i++)
// {
// cout<<0;
// }
// cout<<k-1;}
//}
//#include <fstream>
//#include <iostream>
//using namespace std;
//ifstream fi("intrare.in");
//ofstream fo("iesire.out");
////ifstream fi("produsmaxim.in");
////ofstream fo("produsmaxim.out");
//int main()
//{
// int x,a,b,c;
// while(fi>>x){
// if(x%3==0){
//
// fo<<x<<" "<<x/3<<" "<<x/3<<" "<<x/3<<endl;
// }
// else
// if(x%3==1)
// {
//
// fo<<x<<" "<<x/3<<" "<<x/3<<" "<<x/3+1<<endl;
// }
// else
// fo<<x<<" "<<x/3<<" "<<x/3+1<<" "<<x/3+1<<endl;
// }
//}
////INTERCLASARE
//#include <fstream>
//#include <iostream>
//using namespace std;
////ifstream fi("intrare.in");
////ofstream fo("iesire.out");
//ifstream fi("interclasare.in");
//ofstream fo("interclasare.out");
//int x,a[1000001],b[1000001],c[2000000],n,m,lsol,i,j,k;
//int main()
//{
// fi>>n;
// for(i=1;i<=n;i++)
// fi>>a[i];
// fi>>m;
// for(i=1;i<=m;i++)
// fi>>b[i];
// i=1;
// j=1;
// k=0;
// while(i <= n && j <= m)
// {
// if(a[i] < b[j])
// {
// k++;
// c[k] = a[i];
// i++;
// }
// else
// {
// k++;
// c[k] = b[j];
// j++;
// }
// }
// if(i <= n)
// {
// for(int p = i; p <= n; p++)
// {
// k++;
// c[k] = a[p];
// }
// }
// if(j <= m)
// {
// for(int p = j; p <= m; p++)
// {
// k++;
// c[k] = b[p];
// }
// }
// for(i=1;i<=k;i++)
// {
// if((i-1)%10==0 and i!=1)
// fo<<endl;
// fo<<c[i]<<" ";
// }
//}
//#include <fstream>
//#include <iostream>
//using namespace std;
//ifstream fi("produsxl.in");
//ofstream fo("produsxl.out");
////ifstream fi("intrare.in");
////ofstream fo("iesire.out");
//typedef unsigned long long NrMare[1010];
//unsigned long long x[10000],i,n;
//unsigned long long t,y;
//void ProdusMic(NrMare x, int n)
////x <- x*n
//{
// unsigned long long i,t=0;
// for(i=1;i<=x[0];i++,t/=10)
// {
// t+=x[i]*n;
// x[i]=t%10;
// }
// for(;t;t/=10)
// x[++x[0]]=t%10;
//}
//int main()
//{
// fi>>x[0];
// for(i=x[0];i>=1;i--)
// fi>>x[i];
// fi>>y;
// if(y==0)
// {
// fo<<0;
// return 0;
//
// }
// ProdusMic(x,y);
// for(i=x[0];i>=1;i--)
// fo<<x[i];
//}
//#include <fstream>
//#include <iostream>
//using namespace std;
////ifstream fi("intrare.in");
////ofstream fo("iesire.out");
//ifstream fi("easyquery.in");
//ofstream fo("easyquery.out");
//long long a[100008],b[100008],pi,pf,tip,z,i,n,k;
//int main()
//{
// fi>>n;
// for(i=1;i<=n;i++)
// fi>>a[i];
// fi>>k;
// for(i=1;i<=k;i++)
// {fi>>tip>>pi>>pf>>z;
// if(tip==1)
// {b[pi]+=z;
// b[pf+1]+=-z;}
// else
// {b[pi]-=z;
// b[pf+1]+=z;}
// }
// for(i=1;i<=n;i++)
// b[i]=b[i]+b[i-1];
// for(i=1;i<=n;i++)
// a[i]+=b[i];
// for(i=1;i<=n;i++)
// fo<<a[i]<<" ";
//}
////2084
//#include <iostream>
//using namespace std;
//int a[100003],x,y,r,i,n,j,s,ss;
//int main()
//{
// cin>>n;
// for(i=1;i<=n;i++)
// cin>>a[i];
// r=a[1];
// for(i=1;i<=n;i++)
// if(a[i]<r)
// s=s+r-a[i];
// else
// {ss=ss+s;
// s=0;
// r=a[i];
// }
// s=0;
// r=a[n];
// for(i=n-1;i>=1;i--)
// if(a[i]<=r)
// s=s+r-a[i];
// else
// {ss=ss+s;
// s=0;
// r=a[i];
// }
// cout<<ss;
// return 0;
//}
//#include <fstream>
//#include <iostream>
//using namespace std;
////ifstream fi("intrare.in");
////ofstream fo("iesire.out");
//ifstream fi("mdiferenta.in");
//ofstream fo("mdiferenta.out");
//int n,m,p,q,sol[1000][1000],i,j,x;
//int main()
//{
// fi>>n>>m;
// for(i=1;i<=n;i++)
// for(j=1;j<=m;j++)
// sol[i][j]=0;
// for(i=1;i<=n;i++)
// for(j=1;j<=m;j++)
// {
// fi>>x;
// sol[i][j]+=x;
// }
// fi>>p>>q;
// for(i=1;i<=p;i++)
// for(j=1;j<=q;j++)
// {
// fi>>x;
// sol[i][j]-=x;
// }
// fo<<n<<" "<<m<<'\n';
// for(i=1;i<=n;i++)
// {for(j=1;j<=m;j++)
// fo<<sol[i][j]<<" ";
// fo<<'\n';
// }
// return 0;
//}
//#include <fstream>
//#include <iostream>
//using namespace std;
////ifstream fi("intrare.in");
////ofstream fo("iesire.out");
//ifstream fi("mdiferenta.in");
//ofstream fo("mdiferenta.out");
//void citire(int a[],int &n){
// int i;
// cin>>n;
// for(i=1;i<=n;i++)
// cin>>a[i];
//}
//void afisare(int a[],int n){
// int i;
// for(i=1;i<=n;i++)
// cout<<a[i]<<" ";
//}
//int prim(int x){
// int i;
// if(x==0 or x==1)
// return 0;
// for(i=2;i*i<=x;i++)
// if(x%i==0)
// return 0;
// return 1;
//}
//int urmatorul_prim(int x){
// int nr;
// nr=x+1;
// while(prim(nr)==0)
// nr++;
// return nr;
//}
//void inloc(int a[],int n){
// int i;
// for(i=1;i<=n;i++)
// if(prim(a[i])==0)
// a[i]=urmatorul_prim(a[i]);
//}
//int main()
//{
// int n,a[1000],i;
// citire(a,n);
// inloc(a,n);
// afisare(a,n);
// return 0;
//}
//#include <iostream>
//#include <fstream>
//using namespace std;
//ifstream fi("intrare.in");
//ofstream fo("iesire.out");
////ifstream fi("gogosi.in");
////ofstream fo("gogosi.out");
//long long i,n,j,x,k,sol[1000008],maxi=0,ind;
//int cauta(long long n,long long x[],long long c){
// int st,dr,mij,gasit=0;
// st=1;
// dr=n;
// while(st<=dr)
// {
// mij=st+(dr-st)/2;
// if(x[mij]==c)
// return mij;
// if(x[mij]<c)
// dr=mij-1;
// else
// st=mij+1;
// }
// while(x[mij]<=c and mij>=1)
// mij--;
// return mij+1;
//}
//int main()
//{
// fi>>n;
// if(n==1)
// {
// fo<<1;
// return 0;
// }
// for(i=1;i<=n;i++)
// {
// fi>>x;
// if(i>=2)
// {ind=cauta(n,sol,x);
// sol[ind]=x;}
// else
// sol[1]=x;
// }
// for(i=1;i<=n;i++)
// if(sol[i]==0)
// {
// fo<<i-1;
// return 0;
// }
//}
//#include <iostream>
//#include <fstream>
//using namespace std;
//ifstream fi("intrare.in");
//ofstream fo("iesire.out");
//int n,a[10000],i,s=0;
//int prim(int k){
// int i;
// if(k==0 or k==1)
// return 0;
// for(i=2;i*i<=k;i++)
// if(k%i==0)
// return 0;
// return 1;
//}
//void P(int a[],int n,int &s){
// int i;
// s=0;
// for(i=0;i<n;i++)
// if(prim(a[i]))
// s+=a[i];
//}
//int main()
//{
// fi>>n;
// for(i=0;i<n;i++)
// fi>>a[i];
// P(a,n,s);
// fo<<s;
//}
//
//#include <iostream>
//#include <fstream>
//using namespace std;
//ifstream fi("intrare.in");
//ofstream fo("iesire.out");
//int n,k,c;
//void cnt_cif(int n,int k,int &c){
// if(n>9)
// {
// if(n%10>=k)
// {
// c++;
// cnt_cif(n/10,k,c);
// }
// else
// cnt_cif(n/10,k,c);
// }
// else
// if(n>=k)
// c++;
//}
//int main()
//{
// fi>>n>>k;
// cnt_cif(n,k,c);
// fo<<c;
//}
//#include <iostream>
//#include <fstream>
//using namespace std;
//ifstream fi("intrare.in");
//ofstream fo("iesire.out");
////ifstream fi("interclasare1.in");
////ofstream fo("interclasare1.out");
//int n,i,j,a[1000],b[10000],sol[1000],m,k,maxi,st,dr,ind;
//int main(){
// cin>>n;
// for(i=1;i<=n;i++)
// {
// cin>>a[i];
// }
// i=1;
// while(i<=n ){
// k=0;
// if(a[i]==0)
// { ind=i;
// while(a[i]==0)
// {
// k++;
// i++;
// }}
// else
// i++;
// if(k>maxi)
// {
// st=ind;
// maxi=k;
// dr=i;
// }
// }
// cout<<st<<" "<<dr-1;
//}
//#include <iostream>
//#include <fstream>
//#include <algorithm>
//using namespace std;
//ifstream fi("intrare.in");
//ofstream fo("iesire.out");
////ifstream fi ("numere7.in");
////ofstream fo ("numere7.out");
//int x[200008],cif,i,j,n,m,a,b,st,dr;
//int cautast(int c){
// int li,ls,mij,gasit=0;
// li=1;
// ls=n;
// while(li<=ls)
// {
// mij=ls+(li-ls)/2;
// if(x[mij]==c)
// {if(x[mij-1]==c)
// {while(x[mij]==c)
// mij--;
// return mij;}
// return mij-1;
// }
// if(x[mij]<c)
// li=mij+1;
// else
// ls=mij-1;
// }
// if(x[mij]>=c)
// mij--;
// return mij;
//}
//int cautadr(int c){
// int li,ls,mij,gasit=0;
// li=1;
// ls=n;
// while(li<=ls)
// {
// mij=ls+(li-ls)/2;
// if(x[mij]==c)
// {if(x[mij+1]==c)
// {while(x[mij]==c)
// mij++;
// return mij-1;}
// return mij;
// }
// if(x[mij]<c)
// li=mij+1;
// else
// ls=mij-1;
// }
// if(x[mij]>c)
// mij--;
// return mij;
//}
//int main()
//{
// cin>>n>>m;
// for(i=1;i<=n;i++)
// cin>>x[i];
// sort(x+1,x+n+1);
// for(i=1;i<=m;i++)
// {
// cin>>a>>b;
// st=cautast(a);
// dr=cautadr(b);
// cout<<dr-st<<'\n';
// }
// return 0;
//}
//#include <iostream>
//#include <fstream>
//using namespace std;
//ifstream fi("intrare.in");
//ofstream fo("iesire.out");
////ifstream fi ("punctsegment.in");
////ofstream fo ("punctsegment.out");
//long long x,y,a,b,m,n,s;
//int main()
//{
// cin>>n;
// cout<<n*(n-3)/2<<'\n'<<(n-2)*180;
//}
//#include <iostream>
//#include "Matrice.h"
//using namespace std;
//int verificMaximVecin(Matrice a, int i, int j) {
//int max = -1;
////daca am un vecin in directia respectiva si nu e perete
//if (i > 0 && a.elem[i - 1][j] != 0)
//max = a.elem[i - 1][j];
//if (i < a.n - 1 && a.elem[i + 1][j] != 0)
//if (a.elem[i + 1][j] > max)
//max = a.elem[i + 1][j];
//if (j > 0 && a.elem[i][j - 1] != 0)
//if (a.elem[i][j - 1] > max)
//max = a.elem[i][j - 1];
//if (j < a.m - 1 && a.elem[i][j + 1] != 0)
//if (a.elem[i][j + 1] > max)
//max = a.elem[i][j + 1];
//return max;
//}
////returneaza true daca au mai fost schimbari
//bool gasesteIncaperi(Matrice& a, int& contorIncaperi) {
//int i, j;
//int max;
//bool schimbari = false;
//for (i = 0; i < a.n; i++)
//for (j = 0; j < a.m; j++) {
//if (a.elem[i][j] != 0) {
//max = verificMaximVecin(a, i, j);
////daca minimul e -1, atunci e o incapere inca nedescoperita
//if (max == -1) {
//contorIncaperi++;
//a.elem[i][j] = contorIncaperi;
//schimbari = true;
//}
////altfel, e o camera detectata deja si completez cu numarul ei
////iar daca cumva are mai multe numere, il aleg pe cel mai mare
//else
//if (a.elem[i][j] != max) {
//a.elem[i][j] = max;
//schimbari = true;
//}
//}
//}
//return schimbari;
//}
//15
////returneaza maximul de pe primele l pozitii din vectorul v
//int maximVector(int v[], int l) {
//int max = 0;
//for (int i = 0; i < l; i++)
//if (v[i] > max)
//max = v[i];
//return max;
//}
//int calculeazaAriaMaxima(Matrice a, int contorIncaperi) {
//int ariiCamere[200];
//int i, j;
////initializez toate ariile cu 0;
//for (i = 0; i < contorIncaperi; i++)
//ariiCamere[i] = 0;
//for (i = 0; i < a.n; i++)
//for (j = 0; j < a.m; j++) {
//int idCamera = a.elem[i][j];
////daca e Camera si nu perete ii cresc cu 1 aria
//if (idCamera > 0)
//ariiCamere[idCamera - 1]++;
//}
//return maximVector(ariiCamere, contorIncaperi);
//}
//int main() {
//Matrice a = citire("3.in");
//afisare(a);
//bool schimbari = true;
//int contorIncaperi = 0;
////Cat timp mai sunt schimbari nu putem fi siguri ca o camera e umpluta cu acelasi
////numar, se poate sa nu fi fost detectata din prima parcurgere ca o singura incapere.
////De aceea parcurgem de mai multe ori si daca detectam numere diferite in aceeasi
////incapere le suprascriem cu cel mai mare dintre cele intalnite
//while (schimbari)
//schimbari = gasesteIncaperi(a, contorIncaperi);
//int aria = calculeazaAriaMaxima(a, contorIncaperi);
//cout << "Aria maxima a unei incaperi este: " << aria << endl;
//return 0;
//}
//#include <iostream>
//#include <fstream>
//using namespace std;
//ifstream fi("intrare.in");
//ofstream fo("iesire.out");
////ifstream fi ("punctsegment.in");
////ofstream fo ("punctsegment.out");
//int n,a[1000][1000],sol[100][1000],k,nr,f[100];
//int cpy(int n){
// int i,j;
// for(i=1;i<=n;i++)
// for(j=1;j<=n;j++)
// a[i][j]=sol[i][j];
//}
//int top(int n,int &k){
// int i,j;
// for(i=2;i<n;i++)
// for(j=2;j<n;j++)
// if(a[i-1][j]+a[i+1][j]+a[i][j-1]+a[i][j+1]<3 and a[i][j]!=0)
// {
// sol[i][j]=0;
// k--;}
// else
// sol[i][j]=a[i][j];
// cpy(n);
//}
//int main()
//{
// int i,j;
// cin>>n;
// for(i=1;i<=n;i++)
// for(j=1;j<=n;j++)
// {cin>>a[i][j];
// k+=a[i][j];
// }
// while(k)
// {
// nr++;
// f[nr]=k;
// top(n,k);
// }
// cout<<nr<<'\n';
// for(i=1;i<=nr;i++)
// cout<<f[i]<<'\n';
// return 0;
//}
//
//#include <iostream>
//#include <fstream>
//#include <algorithm>
//using namespace std;
//ifstream fi("intrare.in");
//ofstream fo("iesire.out");
//ifstream fi("porumb.in");
//ofstream fo("porumb.out");
//long long n,pas,i,j,k,s,ok,x,p,aux,l;
//int main()
//{
// fi>>n>>x;
// k=1;
// while(k<=n)
// {
// p++;
// k*=2;
// }
// if(n%2==0)
// fo<<n/2;
// else
// fo<<n/2+1;
// fo<<'\n'<<p<<'\n';
// if(x%2==1)
// fo<<1;
// else
// {
// p=1;
// aux=1;
// while(aux<=x)
// {
// aux*=2;
// p++;
// if(x%aux==0)
// l=p;
// }
// fo<<l;
// }
// fo<<'\n'<<k/2;
// return 0;
//}
////MAJORITAR
//#include <iostream>
//#include <fstream>
//#include <algorithm>
//using namespace std;
//ifstream fi("intrare.in");
//ofstream fo("iesire.out");
////ifstream fi("puterik.in");
////ofstream fo("puterik.out");
//int n,a[100000],b,i,maxi,x,nr1,nr2,k,ok,j,m,r,sol;
//int f(int n, int a[]) {
// int cand = -1, k = 0;
// for (int i = 1; i <= n; i++) {
// if (k == 0) {
// cand = a[i];
// k = 1;
// } else if (a[i] == cand) {
// k++; // nu am putut împerechea pe votantul i şi astfel trebuie să mărim numărul de votanţi necuplaţi
// } else
// k--; // cuplăm votantul i cu orice votant ce îl susţine pe cand şi micşorăm astfel numărul de votanţi necuplaţi
// }
// if (cand < 0)
// return cand;
// // verificare
// int nr = 0;
// for (int i=1; i<=n; i++) {
// if (a[i] == cand)
// nr++;
// }
// if (nr > n / 2)
// return cand;
// else
// return -1;
//}
//int main()
//{
// cin>>n;
// for(i=1;i<=n;i++)
// cin>>a[i];
// sol=f(n,a);
// if(sol!=-1)
// cout<<"DA "<<sol;
// else
// cout<<"NU";
// return 0;
//}
//#include <fstream>
//#include <iostream>
//#include <cmath>
//#include <iomanip>
//using namespace std;
//ifstream fi("intrare.in");
//ofstream fo("iesire.out");
////ifstream fi("secvmax.in");
////ofstream fo("secvmax.out");
//long long n,sol,x,d=2,maxi=0,gata=0,p=0;
//int main(){
// cin>>x;
// while(x!=1 && gata==0){
// p=0;
// while(x%d==0){p++;x=x/d;}
// if(p>0 and p>=maxi)
// {
// maxi=p;
// sol=d;
// }
// d++;
// if(d*d>x)
// gata=1;
// }
// if(x!=1 and maxi==1 or maxi==0)
// cout<<x;
// else
// cout<<sol;
//}
//#include <fstream>
//#include <iostream>
//#include <algorithm>
//#include <iomanip>
//using namespace std;
//ifstream fi("intrare.in");
//ofstream fo("iesire.out");
////ifstream fi("secvmax.in");
////ofstream fo("secvmax.out");
//int n,s,x,aux,i,a[1000];
//int cif(int x){
// int sol=0,p=1;
// while(x){
// if(x%2==0)
// {sol=sol+x%10*p;
// p*=10;}
// x/=10;
// }
// return sol;
//}
//int main(){
// while(fi>>a[++n])
// sort(a+1,a+n+1);
// for(i=1;i<=n;i++)
// if(a[i]%2==1 and a[i+1]!=a[i])
// fo<<a[i]<< " ";
// fo<<endl;
// for(i=n-1;i>=1;i--)
// if(a[i]%2==0 and a[i-1]!=a[i])
// fo<<a[i]<<" ",s+=a[i];
//fo<<endl;
//fo<<cif(s);
//}
//#include <fstream>
//#include <iostream>
//using namespace std;
//ifstream fi("intrare.in");
//ofstream fo("iesire.out");
//ifstream fi("sumcolmax.in");
//ofstream fo("sumcolmax.out");
//long long n,s,m,x,aux,c,i,j,a[1000][1000],maxi,ind,sol;
//int main(){
// fi>>n>>m;
// maxi=-100000000;
// for(i=1;i<=n;i++)
// for(j=1;j<=m;j++)
// fi>>a[i][j];
// for(i=1;i<=m;i++)
// {
// s=0;
// for(j=1;j<=n;j++)
// s=s+a[j][i];
// if(s>maxi)
// {
// maxi=s;
// sol=i;
// }
// }
// for(i=1;i<=n;i++)
// fo<<a[i][sol]<<" ";
//}
//#include <fstream>
//#include <iostream>
//#include <algorithm>
////#define fi cin
////#define fo cout
//using namespace std;
//ifstream fi("intrare.in");
//ofstream fo("iesire.out");
////ifstream fi("exista.in");
////ofstream fo("exista.out");
//int n,i,a[1000];
//int main(){
// cin>>n;
// for(i=1;i<=n;i++)
// cin>>a[i];
// i=1;
// for(i=1;i<n;i++){
// cout<<a[i]<<" ";
// if ((a[i]%2==0&&a[i+1]%2==0)||(a[i]%2!=0&&a[i+1]%2!=0))
// cout<<(a[i]+a[i+1])/2<<" ";
// }
// cout<<a[i];
//}
//#include <iostream>
//#include <cmath>
//#include <fstream>
//using namespace std;
////ifstream fi("intrare.in");
////ofstream fo("iesire.out");
//ifstream fi("spirala.in");
//ofstream fo("spirala.out");
//int a[100][100],i,j,n,m,k,sol;
//void stdr(int n,int ind){
// for(i=ind;i<=n-ind+1;i++)
// fo<<a[ind][i]<<" ";
//}
//void drst(int n,int ind){
// for(i=n-ind;i>=ind+1;i--)
// fo<<a[n-ind+1][i]<<" ";
//}
//void susjos(int n,int ind){
// for(i=ind+1;i<=n-ind+1;i++)
// fo<<a[i][n-ind+1]<<" ";
//}
//void jossus(int n,int ind){
// for(i=n-ind+1;i>=ind+1;i--)
// fo<<a[i][ind]<<" ";
//}
//int main()
//{
// fi>>n;
// for (i=1;i<=n;i++)
// for(j=1;j<=n;j++)
// fi>>a[i][j];
// k=0;
// sol=1;
// while(k<=n*2-1){
// if(k<=n*2-1)
// stdr(n,sol);
// k++;
// if(k<=n*2-1)
// susjos(n,sol);
// k++;
// if(k<=n*2-1)
// drst(n,sol);
// k++;
// if(k<=n*2-1)
// jossus(n,sol);
// sol++;
// }
//}
//#include <iostream>
//#include <fstream>
//using namespace std;
//ifstream fi("intrare.in");
//ofstream fo("iesire.out");
//int i,n,k,nr1,aux,p,nrcif;
//int cmmdc(int a,int b)
//{
// int r;
// r = a % b;
// while(r != 0)
// {
// a = b;
// b = r;
// r = a % b;
// }
// return b;
//}
//int main(){
// int st,dr;
// cin>>n;
// aux=n;
// p=1;
// while(aux)
// {
// nrcif++;
// aux/=10;
// }
// while(k<=nrcif/2-1)
// {
// nr1=nr1+n%10*p;
// p*=10;
// k++;
// n/=10;
// }
// if(nrcif%2==1)
// n=n/10;
// if(nr1==0)
// {cout<<0;return 0;}
// else
// cout<<cmmdc(n,nr1);
//
//}
//#include <iostream>
//#include <math.h>
//#include <fstream>
//using namespace std;
//ifstream fi("intrare.in");
//ofstream fo("iesire.out");
//int div(long long x)
//{
// long long d=2,sol=1;
// for(d=2;d*d<x;d++)
// if(x%d==0)
// {
// if(d%2==0)
// {sol++;}
// if((x/d)%2==0)
// sol++;//fo<<x/2<<"2 ";}
// }
// if(d*d==x and d%2==0)
// sol++;
// return sol;
//}
//int main(){
// long long n,a,b,i,k,maxi=-21470000,nr1=0,nr2=0;
// cin>>a>>b;
// for(i=a+a%2;i<=b;i+=2)
// {
// k=div(i);
// if(k>maxi)
// {
// maxi=k;
// nr1=nr2=i;
// }
// else
// if(k==maxi)
// nr2=i;
// }
// cout<<maxi<<" "<<nr1<<" "<<nr2;
//}
//#include <fstream>
//#include <iostream>
//#include <algorithm>
//using namespace std;
//ifstream fi("intrare.in");
//ofstream fo("iesire.out");
////ifstream fi("divigrup.in");
////ofstream fo("divigrup.out");
//int dis[10000],d[10000],q[10000],i,n,c,s,ferm,sol,cant;
//int dist(int n,int d[10000]){
// int i;
// dis[1]=d[0];
// for(i=2;i<=n+1;i++)
// dis[i]=d[i-1]+dis[i-1];
//}
//int main()
//{
// fi>>n>>c;
// for(i=0;i<=n;i++)
// fi>>d[i];
// for(i=1;i<=n;i++)
// fi>>q[i];
// dist(n,d);
// ferm=1;
// cant=c;
// while(ferm<=n)
// {
// while(q[ferm]>0)
// {
// sol+=min(dis[ferm],dis[n+1]-dis[ferm]);//<<endl;
// q[ferm]=q[ferm]-cant;
// if(q[ferm]>0)
// cant=c;
// }
// if(q[ferm]<0)
// cant=-q[ferm];
// sol+=min(d[ferm],dis[n+1]-dis[ferm])
// ferm++;
// }
// fo<<sol;
// return 0;
//}
//#include <iostream>
//using namespace std;
//int main(){
// int n,i,j,k,b,c=0,ok=1;
// cin >> n;
// int v[n],a[n];
// for(i=1;i<=n;i++)
// cin >> v[i];
// for(i=1;i<=n;i++)
// cin >> a[i];
// for(i=1;i<=n;i++){
// b=v[i];
// k=0;
// c=0;
// for(j=1;j<=n;j++){
// if(b==a[j]) k++;
// if(b==v[j]) c++;
// }
// if(c!=k) ok=0;
// }
// if(ok)
// cout<<"DA";
// else
// cout<<"NU";
// return 0;
//}
//
//#include <fstream>
//#include <iostream>
//#include <algorithm>
//using namespace std;
//ifstream fi("intrare.in");
//ofstream fo("iesire.out");
////ifstream fi("divigrup.in");
////ofstream fo("divigrup.out");
//int n,i,x,p,a[10000],maxi,mini,pozmax,pozmin;
//void sortare (int n,int k[],int st,int dr){
// int i,j,a;
// i=st;
// j=dr;
// a=k[i];
// do{
// while(k[j]>=a and i<j)
// j=j-1;
// k[i]=k[j];
// while(k[i]<=a and i<j)
// i=i+1;
// k[j]=k[i];
// }while(i!=j);
// k[i]=a;
// if(st<i-1)
// sortare(n,k,st,i-1);
// if(i+1<dr)
// sortare(n,k,i+1,dr);
//}
//int main()
//{
// mini=10000000;
// cin>>n;
// for(i=1;i<=n;i++)
// {cin>>a[i];
// if(a[i]>maxi)
// maxi=a[i],pozmax=i;
// }
// sortare(n,a,1,pozmax);
// sortare(n,a,pozmax+1,n);
// for(i=1;i<=pozmax;i++)
// cout<<a[i]<<" ";
// for(i=n;i>pozmax;i--)
// cout<<a[i]<<" ";
// return 0;
//}
//#include <fstream>
//#include <iostream>
//#include <algorithm>
//using namespace std;
//ifstream fi("intrare.in");
//ofstream fo("iesire.out");
////ifstream fi("divigrup.in");
////ofstream fo("divigrup.out");
//int n,i,j,v[100008],st[3][100008];
//int main()
//{
// fi>>n;
// for(i=1;i<=n;i++)
// {
// fi>>v[i];
// while(v[i]>st[1][j] and j>=1)
// {
// v[st[2][j]]=v[i];
// j--;
// fo<<st[1][j]<< " "<<st[2][j]<<" ";
// }
// fo<<endl;
// j++;
// st[1][j]=v[i];
// st[2][j]=i;
// }
// for(i=1;i<=j;i++)
// v[st[2][i]]=-1;
//// for(i=1;i<=n;i++)
//// cout<<v[i]<<" ";
// return 0;
//}
//#include <fstream>
//#include <iostream>
//#include <algorithm>
//#include <iomanip>
//using namespace std;
////ifstream fi("intrare.in");
////ofstream fo("iesire.out");
//ifstream fi("nrlipsa2.in");
//ofstream fo("nrlipsa2.out");
//int n,i,j,poz[1000],neg[1000],x;
//float sol,s,k;
//int main()
//{
// while(fi>>x){
// if(x<0 and x>=-100)
// neg[-x]++;
// else
// if(x>=0 and x<=100)
// poz[x]++;
// }
// for(i=100;i>0;i--)
// if(neg[i]==0)
// {
// fo<<-i;
// return 0;
// }
// for(i=0;i<=100;i++)
// if(poz[i]==0)
// {
// fo<<i;
// return 0;
// }
// fo<<"nu exista";
// return 0;
//}
//
//#include <fstream>
//#include <iostream>
//#include <algorithm>
//#include <iomanip>
//using namespace std;
////ifstream fi("intrare.in");
////ofstream fo("iesire.out");
//ifstream fi("nrlipsa2.in");
//ofstream fo("nrlipsa2.out");
//int n,i,j,poz[1000],neg[1000],x;
//int main()
//{
// cin>>n;
// for(i=1;i<=n;i++)
// cin>>a[i];
//
// return 0;
//}
//#include <fstream>
//#include <iostream>
//using namespace std;
//ifstream fi("intrare.in");
//ofstream fo("iesire.out");
////ifstream fi("nrlipsa2.in");
////ofstream fo("nrlipsa2.out");
//int n,i,a[10000],k;
//void F(int &n,int a[],int &k){
// if(n==0)
//
// {if(a[n-1]%2==0)
// {
// while(a[n-1]<=k)
// a[n-1]*=10;
// k+=a[n-1];
// }
// n=n-1;
// F(n,a,k);
// }
//}
//int main()
//{
// fi>>n;
// for(i=1;i<=n;i++)
// fi>>a[i];
// F(n,a,k);
// fo<<k;
// return 0;
//}
//#include <iostream>
//#include <fstream>
//using namespace std;
//ifstream fi("intrare.in");
//ofstream fo("iesire.out");
//int prim(int x){
// int i;
// if(x==0 or x==1)
// return 0;
// for(i=2;i*i<=x;i++)
// if(x%i==0)
// return 0;
// return 1;
//}
//void P(int a[],int n,int &s){
// int ok=1,i;
// if(n==1)
// {
// if(a[n-1]==0 or a[n-1]==1)
// ok=0;
// for(i=2;i*i<=a[n-1];i++)
// if(a[n-1]%i==0)
// ok=0;
// if(ok==1)
// s+=a[n-1];
// }
// else
// {
// if(a[n-1]==0 or a[n-1]==1)
// ok=0;
// for(i=2;i*i<=a[n-1];i++)
// if(a[n-1]%i==0)
// ok=0;
// if(ok==1)
// s+=a[n-1];
// P(a,n-1,s);
// }
//}
//int main()
//{
//
// int n,a[10],i,rez,s=0;
// fi>>n;
// for(i=0; i<n; i++)
// fi>>a[i];
// P(a,n,s);
// fo<<s;
// return 0;
//}
//#include <iostream>
//#include <fstream>
//using namespace std;
//ifstream fi("intrare.in");
//ofstream fo("iesire.out");
////ifstream fi("palindrom_ciclic.in");
////ofstream fo("palindrom_ciclic.out");
//int nrUnu(int x){
// int r,sol=0;
// while(x)
// {
// r=x%2;
// if(r==1)
// sol++;
// x/=2;
// }
// return sol;
//}
//void nrGr(int b[],int n){
// int i,nrGr=0;
// for(i=2;i<=n;i++)
// if(b[i]!=b[i-1])
// nrGr++;
// fo<<nrGr+1<<endl;
//}
//void citire(int &n,int a[],int b[]){
// int i;
// fi>>n;
// for(i=1;i<=n;i++)
// {fi>>a[i];
// b[i]=nrUnu(a[i]);
// }
//}
//void sortare(int n,int a[],int b[]){
// int i,j;
// for(i=1;i<=n;i++)
// for(j=i+1;j<=n;j++)
// if(b[i]>b[j])
// swap(a[i],a[j]),swap(b[i],b[j]);
//}
//void afisare(int n,int a[],int b[]){
// int i;
// for(i=1;i<=n;i++)
// if(b[i]!=b[i+1])
// fo<<a[i]<<'\n';
// else
// fo<<a[i]<<" ";
//}
//int main()
//{
// int n,a[101],i,b[101],j;
// citire(n,a,b);
// sortare(n,a,b);
// nrGr(b,n);
// afisare(n,a,b);
// return 0;
//}
//#include <iostream>
//#include <fstream>
//using namespace std;
//ifstream fi("intrare.in");
//ofstream fo("iesire.out");
////ifstream fi("palindrom_ciclic.in");
////ofstream fo("palindrom_ciclic.out");
//long long d,aux,gata,x;
//int main(){
// cin>>x;
// aux=x;
// d=2;
// while(x!=1&& gata==0){
// while(x%d==0)
// x=x/d;
// d++;
// if(d*d>x)
// gata=1;
// }
// if(x>1)
// cout<<x;
// else
// cout<<d-1;
//}
//#include <iostream>
//#include <fstream>
//#include <algorithm>
//using namespace std;
//ifstream fi("intrare.in");
//ofstream fo("iesire.out");
////ifstream fi("puterik.in");
////ofstream fo("puterik.out");
//int n,a[100000],b,i,maxi,x,nr1,nr2,k,ok,j,m,r;
//int main()
//{
// cin>>n;
// for(i=1;i<=n;i++)
// cin>>a[i];
// sort(a+1,a+n+1);
// k=1;
// for(i=1;i<n;i++)
// {
// if(a[i]==a[i+1])
// {k++;
// if(k>n/2)
// {
// cout<<"DA "<<a[i];
// return 0;
// }
// }
// else
// k=0;
// }
// cout<<"NU";
// return 0;
//}
//#include <iostream>
//#include <fstream>
//#include <cmath>
//using namespace std;
////ifstream fi("intrare.in");
////ofstream fo("iesire.out");
//ifstream fi("chibrituri.in");
//ofstream fo("chibrituri.out");
//int vert[10],oriz[10],i,j,n,a[100][100],k,sol,ind,m,x;
//int main()
//{
// fi>>n;
// fi>>m;
// vert[0]=4;
// oriz[0]=2;
// vert[1]=2;
// oriz[1]=0;
// vert[2]=2;
// oriz[2]=3;
// vert[3]=2;
// oriz[3]=3;
// vert[4]=3;
// oriz[4]=1;
// vert[5]=2;
// oriz[5]=3;
// vert[6]=3;
// oriz[6]=3;
// vert[7]=2;
// oriz[7]=1;
// vert[8]=4;
// oriz[8]=3;
// vert[9]=3;
// oriz[9]=3;
// //ora
// for(i=0;i<=2;i++)
// if(i<2)
// for(j=0;j<=9;j++)
// {
// a[1][i*10+j]=vert[i]+vert[j];
// a[2][i*10+j]=oriz[i]+oriz[j];
// }
// else
// for(j=0;j<=3;j++)
// {
// a[1][i*10+j]=vert[i]+vert[j];
// a[2][i*10+j]=oriz[i]+oriz[j];
// }
//
// for(i=0;i<=5;i++)
// for(j=0;j<=9;j++)
// {
// a[1][i*10+j]=vert[i]+vert[j];
// a[2][i*10+j]=oriz[i]+oriz[j];
// }
//// for(i=1;i<=2;i++)
//// {for(j=0;j<=24;j++)
//// fo<<j<<" "<<a[i][j]<<" ";
//// fo<<endl;
//// }
//bool ok=0;
//int sol1i,sol1j,sol2i,sol2j;
// for(i=0;i<=23;i++)
// for(j=0;j<=59;j++)
// if((a[1][i]+a[1][j])==n and (a[2][j]+a[2][i])==m)
// {
// if(ok==0)
// {
// sol1i=i;
// sol1j=j;
// sol2i=i;
// sol2j=j;
// ok=1;
// }
// else
// {
// sol2i=i;
// sol2j=j;
// }
// k++;
// }
// fo<<k<<'\n';
// if(sol1i<10)
// fo<<0;
// fo<<sol1i<<":";
// if(sol1j<10)
// fo<<0;
// fo<<sol1j<<'\n';
// if(sol2i<10)
// fo<<0;
// fo<<sol2i<<":";
// if(sol2j<10)
// fo<<0;
// fo<<sol2j;
// return 0;
//}
//#include <fstream>
//#include <iostream>
//#include <algorithm>
//using namespace std;
////ifstream fi("intrare.in");
////ofstream fo("iesire.out");
//ifstream fi("divigrup.in");
//ofstream fo("divigrup.out");
//int n, i,m,a[1000],b[10000],sol,j,fr[1000],l;
//int nrdiv(int x){
// int exp=0,nr_div=0;
// while(x%2==0)
// {
// exp++;
// x/=2;
// }
// nr_div=exp+1;
// int d=3;
// while(d*d<=x)
// {
// exp=0;
// while(x%d==0)
// {
// exp++;
// x/=d;
// }
// nr_div*=(exp+1);
// d+=2;
// }
// if(x!=1)
// nr_div*=2;
// return nr_div;
//}
//int main()
//{
// int k=0,aux;
// fi>>n;
// for(i=1;i<=n;i++)
// {
// fi>>a[i];
// sol=nrdiv(a[i]);
// fr[sol]++;
// b[i]=sol;
// if(sol>m)
// m=sol;
// if(fr[sol]==1)
// k++;
// }
// for(i=1;i<=n;i++)
// for(j=i;j<=n;j++)
// if(b[i]>b[j])
// {
// swap(a[i],a[j]);
// swap(b[i],b[j]);
// }
// else
// if(b[i]==b[j])
// if(a[i]<a[j])
// swap(a[i],a[j]);
//// for(i=1;i<=n;i++)
//// if(fr[i])
//// fo<<fr[i]<<" ";
// fo<<k<<'\n';
// j=n;
// for(i=m;i>=1;i--)
// if(fr[i])
// {
// fo<<fr[i]<<" ";
// for(;j>=1 and b[j]==i;j--)
// fo<<a[j]<<" ";
// fo<<'\n';
// }
// return 0;
//}
//#include <iostream>
//#include <fstream>
//using namespace std;
//ifstream fi("intrare.in");
//ofstream fo("iesire.out");
////ifstream fi("prim013.in");
////ofstream fo("prim013.out");
//int q,p,n,nr,a[100],i,k,c,sol,nrcif;
//int main(){
// fi>>n>>c;
// if(c>n)
// {
// fo<<0;
// return 0;
// }
// while(n)
// a[++k]=n%10,n/=10;
// for(i=1;i<k;i++)
// {
// nrcif+=9;
// if(i>2)
// nrcif*=10;
// sol+=nrcif;
// }
// for(i=1;i<=k;i++)
//
// fo<<sol;
//}
//#include <fstream>
//#include <iostream>
//#include <cmath>
//#include <algorithm>
//using namespace std;
//ifstream fi("intrare.in");
//ofstream fo("iesire.out");
////ifstream fi("cifre15.in");
////ofstream fo("cifre15.out");
//int a,b,c;
//int f(int n,int i){
// int aux=pow(2,n-i+1);
// while()
//}
//int main()
//{
// fi>>n;
// f(n);
// return 0;
//}
//#include <fstream>
//#include <iostream>
//#include <cmath>
//#include <algorithm>
//using namespace std;
//ifstream fi("intrare.in");
//ofstream fo("iesire.out");
//int a,b;
//int f(int a,int b)
//{
// if(a<=0 or b<=0)
// return 1;
// else
// return a*b+f(a-1,b-1);
//}
//
//int main()
//{
// int n;
// cin >> a>>b;
// cout<<f(a,b);
// return 0;
//}
//#include <fstream>
//#include <algorithm>
//#include <cmath>
//using namespace std;
//ifstream fi("intrare.in");
//ofstream fo("iesire.out");
////ifstream fi("joc20.in");
////ofstream fo("joc20.out");
//int n,i,a[100002],mini[100002],st,dr,pas,sumA,sumT,m;
//
//int main() {
// fi>>n>>m;
// for(i=1;i<=n;i++)
// fi>>a[i];
// sort(a+1,a+n+1);
// for(i=1;i<=n;i++)
// fo<<a[i]<<" ";
// fo<<endl;
// //citire
// pas=1;
// for(i=1;i<=100000;i++)
// if(i<=a[pas])
// mini[i]=a[pas];
// else
// {while(a[pas]<i)
// pas++;
// mini[i]=a[pas];
// }
// for(i=1;i<=m;i++)
// {
// fi>>st>>dr;
// fo<<mini[st]<<endl;
// }
// return 0;
//}
//#include <iostream>
//#include <fstream>
//using namespace std;
//ifstream fi("intrare.in");
//ofstream fo("iesire.out");
//ifstream fi("joc20.in");
//ofstream fo("joc20.out");
//int i,j,a[4000],sol,k,n,dr,st,maxi,b[4000],sumA,sumT;
//int main() {
// fi>>n;
// for(i=1;i<=n;i++)
// fi>>a[i];
// for(i=1;i<=n;i++)
// fi>>b[i];
// st=1;
// dr=n;
// for(i=1;i<=n;i++)
// {
// if(i%2==1)
// {
// if(b[i]==1)
// sumA+=a[st++];
// else
// sumA+=a[dr--];
// }
// else
// {
// if(b[i]==1)
// sumT+=a[st++];
// else
// sumT+=a[dr--];
// }
// }
// if(sumA>sumT)
// fo<<sumA<<" "<<1;
// else
// if(sumA<sumT)
// fo<<sumT<<" "<<2;
// else
// fo<<sumA<<" "<<0;
// return 0;
//}
//#include <iostream>
//#include <fstream>
//using namespace std;
////ifstream fi("intrare.in");
////ofstream fo("iesire.out");
//ifstream fi("romane.in");
//ofstream fo("romane.out");
//int i,j,lit[6],nrc,c,k,n,dr,st,maxck,ap[40000],aux;
//int unit(int x){
// if(x!=0)
// {
// if(x<=3)
// lit[1]+=x;
// else
// if(x<=8 and x>3)
// {
// lit[2]++;
// if(x==4)
// lit[1]++;
// else
// {
// lit[1]=lit[1]+x%5;}
// }
// else
// {
// lit[3]++;
// lit[1]++;
// }
// }
//}
//int zeci(int x){
//if(x!=0)
// {
// if(x<=3)
// lit[3]+=x;
// else
// if(x<=8 and x>3)
// {
// lit[4]++;
// if(x==4)
// lit[3]++;
// else
// {
// lit[3]=lit[3]+x%5;}
// }
// else
// {
// lit[5]++;
// lit[3]++;
// }
// }
//}
//int sute(int x){
// lit[5]+=x;
//}
//int main()
//{
// fi>>n;
// for(i=1;i<=n;i++)
// {
// aux=i;
// k=1;
// while(aux)
// {
// if(k==1)
// unit(aux%10);
// else
// if(k==2)
// zeci(aux%10);
// else
// sute(aux%10);
// k++;
// aux/=10;
// }
// }
// for(i=1;i<=5;i++)
// fo<<lit[i]<<" ";
// return 0;
//}
//#include <iostream>
//#include <algorithm>
//#include <fstream>
//#include <cstring>
//using namespace std;
////ifstream fi("intrare.in");
////ofstream fo("iesire.out");
//ifstream fi("colier.in");
//ofstream fo("colier.out");
//int i,n,a[50001],sol1,j,b[50001],T,ok,nr,st;
//int schi(int x){
// int mini,maxi,k=0,ind1=0,ind2=0;
// mini=10;
// maxi=0;
// while(x){
// if(x%10>maxi)
// maxi=x%10,ind1=k;
// if(x%10<mini)
// mini=x%10,ind2=k;
// k++;
// x/=10;
// }
// if(ind1>ind2)
// return maxi*10+mini;
// else
// return mini*10+maxi;
//}
//int main()
//{
// fi>>T>>n;
// for(i=1;i<=n;i++)
// {
// fi>>a[i];
// a[i]=schi(a[i]);
// if(a[i]%10>a[i]/10)
// b[i]=1;
// else
// b[i]=2;
// if(T==1)
// if(b[i]==1)
// sol1++;
// }
// if(T==1)
// fo<<sol1;
// else
// {
// nr=n;
// st=1;
// b[n+1]=b[1];
// while(st<=n)
// {
// if(b[st]==b[st+1])
// {
// nr--;
// }
// st++;
// }
// fo<<nr+(nr==0);
// }
//}
//#include <fstream>
//#include <iostream>
//#include <cstring>
//#include <iomanip>
//using namespace std;
//ifstream fi("intrare.in");
//ofstream fo("iesire.out");
//int lin,col,i,j,n,m,x[2],c[2];
//char s[256],sep[]="=",*bc,*nr,sep1[]="-+";
//int main()
//{
// fi>>n;
// fi.getline(s,256);
// for(i=1;i<=n;i++)
// {
// fi.getline(s,258);
// bc=strtok(s,sep);
// nr=strtok(bc,sep1);
// while(nr){
// fo<<nr<<" ";
// nr=strtok(0,sep1);
// }
// fo<<endl;
// }
//}
#include <fstream>
#include <iostream>
#include <cstring>
#include <iomanip>
using namespace std;
//ifstream fi("intrare.in");
//ofstream fo("iesire.out");
ifstream fi("fructe.in");
ofstream fo("fructe.out");
int n,i,p,b;
int main()
{
fi>>n;
for(i=1;i<=n;i++)
{
fi>>p>>b;
if(b%2==0)
fo<<0<<'\n';
else
fo<<1<<'\n';
}
}
Moldovan Andrei Ioan thePunisher