XOR Clique

BaoBao has a sequence a​1​,a​2,...,a​n. He would like to find a subset S of {1,2,...,n} such that ∀i,j∈S, a​i ⊕a​j<min(ai ,aj) and ∣S∣ is maximum, where ⊕ means bitwise exclusive or.

Input

There are multiple test cases. The first line of input contains an integer T, indicating the number of test cases. For each test case:

The first line contains an integer n (1≤n≤100000), indicating the length of the sequence.

The second line contains n integers: a​1​​ ,a​​2​ ,...,a​n(1≤ai≤10的9次方), indicating the sequence.

It is guaranteed that the sum of n in all cases does not exceed 100000.

Output

For each test case, output an integer denoting the maximum size of S.

Sample Input

3

3

1 2 3

3

1 1 1

5

1 2323 534 534 5

Sample Output

2

3

2

题意，求在a数组中找出s子集，要求子集中任意两个数异或之后比这两个数都小，求最大子集里面元素的个数；

可以知道，2进制的0和1异或才是1，其他是0，要求两个数异或要更小，则必须两个相同长度的数二进制的最高位要都是1，所以，只需要知道在每个长度的集合中，存在多少个元素，元素最多的那个就是答案；

例3中，对应的log2(x)为0，11，9，9，2，可以得到534和534在长度9的子集中，最大子集元素个数为2；

#include<iostream>

#include<algorithm>

#include<string.h>

#include<cmath>

#include<map>

using namespace std;

map<int,int>m;//记录符合条件的子集元素个数

int main()

{

         //init();

         int T;

         scanf("%d",&T);

         while(T--)

         {

                  m.clear();

                  int n,x;

                  scanf("%d",&n);

                  while(n--){

                           scanf("%d",&x);

                           m[log2(x)]++;//求二进制位数并记录出现次数

                  }

                  int cnt=0;

                  map<int,int>::iterator it;

                  for(it=m.begin();it!=m.end();it++)

                           cnt=max(cnt,it->second);//求m中最大值

                  printf("%d\n",cnt);

         }

         return 0;

}

/*

log2(x)求法

int w[31];

void init(){

         for(int i=0;i<30;i++)

                  w[i]=1<<i;

}

int find(int x)

{

         int l=0,r=30;

         while(r-l>1)

         {

                  int mid=l+r>>1;

                  if(w[mid]<=x)

                           l=mid;

                  else   r=mid;

         }

         if(w[r]<x)

                  return r;

         else

                  return l;

}*/