using System; using System.Collections; using System.Collections.Generic; class TEST{ static void Main(){ Sol mySol =new Sol(); mySol.Solve(); } } class Sol{ public void Solve(){ int[] gr=new int[N+1]; gr[1]=0; for(int i=2;i<=N;i++){ HashSet H=new HashSet(); if(i%2==0){ H.Add(gr[i/2]^gr[i/2]); }else{ H.Add(gr[i/2]^gr[1+i/2]); } if(i>=3){ if(i%3==0){ H.Add(gr[i/3]^gr[i/3]^gr[i/3]); }else if(i%3==1){ H.Add(gr[1+i/3]^gr[i/3]^gr[i/3]); }else{ H.Add(gr[1+i/3]^gr[1+i/3]^gr[i/3]); } } for(int j=1;jint.Parse(e));} static long[] rla(){return Array.ConvertAll(Console.ReadLine().Split(' '),e=>long.Parse(e));} static double[] rda(){return Array.ConvertAll(Console.ReadLine().Split(' '),e=>double.Parse(e));} }