题目描述

乔纳森正在与迪奥的吸血鬼手下战斗。其中有 $n$ 个吸血鬼，它们的强度分别为 $a_1, a_2,\cdots, a_n$。 将 $(l,r)$ 表示由索引 $l$ 到 $r$ 的吸血鬼组成的一组。乔纳森意识到每个这样的组的强度取决于它们的最弱环节，即按位与操作。更具体地说，组 $(l,r)$ 的强度等于 $f(l,r) =$ $a_l \ \& \ a_{l+1} \ \& \ a_{l+2} \ \& \cdots \& \ a_r$。这里，$\&$ 表示按位与操作。

乔纳森希望能快速击败这些吸血鬼手下，因此他会将吸血鬼分成连续的组，使得每个吸血鬼正好属于一组，并且这些组的强度之和尽量小。在所有可能的分组方式中，他希望找到组数最多的方式。

给定每个吸血鬼的强度，找出在所有可能的分组方式中，拥有最小强度之和的组的最大数量。

输入格式

第一行包含一个整数 $t$ $(1 \le t \le 10^4)$，表示测试用例的数量。接下来是每个测试用例的描述。

每个测试用例的第一行包含一个整数 $n$ $(1 \le n \le 2⋅10^5)$，表示吸血鬼的数量。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \cdots, a_n$ $(0 \le a_i \le 10^9)$，表示每个吸血鬼的个体强度。

所有测试用例中 $n$ 的总和不超过 $2⋅10^5$。

输出格式

对于每个测试用例，输出一个整数，表示在所有可能的分组方式中，拥有最小强度之和的组的最大数量。

样例解释

在第一个测试用例中，最优的方式是将所有的吸血鬼作为一组。所以 $f(1,3) =$$1 \ \& \ 2 \ \& \ 3 = 0$。

在第二个测试用例中，最优的方式是分成两组，$(2,3,1)$ 和 $(5,2)$。所以 $f(1,3) + f(4,5) = (2 \ \& \ 3 \ \& \ 1) + (5 \ \& \ 2) = 0 + 0 = 0$。

Translate by

样例

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

1
2
1