You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Description

$cjx$正在与怪物对战，怪物有$n$个，怪物的实力分别为为$a_{1},a_{2},...,a_{n}$。
设$(l,r)$为编号为$l$到编号为$r$的怪物组成的群体，$cjx$意识到一组怪物的综合实力取决于该群体中所有怪物实力相与。
即：对于一个怪物群体$(l,r)$，其综合实力为$f(l,r)$,其中$f(l,r)$定义为：

这里的$\&$表示按位与。
因为$cjx$想尽快打败所有怪物，所以他将所有怪物分成连续的群体，使得每只怪物都属于且仅属于一个群体，同时使所有组的综合实力之和最小，此外 $cjx$希望找到分组数量最多的方法。
即：给定$n$只怪物的实力$a_{1},a_{2},...,a_{n}$，在使得所有组的综合实力之和最小的前提下，找到最多的分组数量。

Format

Input

第一行：一个整数$T$ $(1\leq T\leq 10^3)$，表示$cjx$要进行$T$场战斗。
每次战斗描述如下：
第一行：一个整数$n$ $(1\leq n\leq 10^5)$，本次战斗中怪物的数量。
第二行：$n$个整数$a_{1},a_{2},...,a_{n}$ $(1\leq a_{i}\leq 10^9)$，表示每个怪物的实力。

Output

$T$行，每行一个整数，表示在第$i$次战斗中，在使得每组的综合实力最弱的前提下，最多的分组数量。

Samples

3
3
1 2 3
5
2 3 1 5 2
4
5 7 12 6

1
2
1

Hints

第二场战斗中，符合题意的分组方法是分成两组$(1,3)和(4,5),即\{2,3,1\}\{5,2\}$，这样，第一组的综合实力$f(1,3)=2\&3\&1=0$，第二组的综合实力$f(4,5)=5\&2=0$，所以，在使得所有组的综合实力之和最小的前提下，最多的分组数量为2。

Limitation

1s, 256MiB for each test case.