CF1847B.Hamon Odyssey

Jonathan is fighting against DIO's Vampire minions. There are $n$ of them with strengths $a_1, a_2, \dots, a_n$. $\def\and {{\,\texttt{&}\,}}$

Denote $(l, r)$ as the group consisting of the vampires with indices from $l$ to $r$. Jonathan realizes that the strength of any such group is in its weakest link, that is, the bitwise AND. More formally, the strength level of the group $(l, r)$ is defined as $$f(l,r) = a_l \and a_{l+1} \and a_{l+2} \and \ldots \and a_r.$$ Here, \and denotes the bitwise AND operation.

Because Jonathan would like to defeat the vampire minions fast, he will divide the vampires into contiguous groups, such that each vampire is in exactly one group, and the sum of strengths of the groups is minimized. Among all ways to divide the vampires, he would like to find the way with the maximum number of groups.

Given the strengths of each of the $n$ vampires, find the maximum number of groups among all possible ways to divide the vampires with the smallest sum of strengths.

乔纳森正在与迪奥的吸血鬼仆从作战。一共有 $n$ 个吸血鬼，其力量值分别为 $a_1, a_2, \dots, a_n$。$\def\and {{\,\texttt{&}\,}}$

记 $(l, r)$ 为由下标从 $l$ 到 $r$ 的吸血鬼组成的群体。乔纳森意识到，任一群体的力量取决于其中最弱的一环，即按位与（bitwise AND）运算。更准确地说，群体 $(l, r)$ 的力量值定义为

$$f(l,r) = a\_l \\and a\_{l+1} \\and a\_{l+2} \\and \\ldots \\and a\_r.$$

此处，\and 表示按位与运算。

由于乔纳森希望尽快击败这些吸血鬼仆从，他将把所有吸血鬼划分为若干连续的群体，使得每个吸血鬼恰好属于一个群体，且所有群体的力量值之和最小。在所有能使力量值之和达到最小的划分方案中，他希望找到群体数量最多的那一种。

给定 $n$ 个吸血鬼各自的力量值，请找出：在所有能使力量值之和最小的划分方案中，所能达到的最大群体数量。

The first line contains a single integer $t$ $(1 \leq t \leq 10^4)$ — the number of test cases. The description of test cases follows.

The first line of each test case contains a single integer $n$ ($1 \leq n \leq 2 \cdot 10^5$) — the number of vampires.

The second line of each test case contains $n$ integers $a_1,a_2,\ldots,a_n$ ($0 \leq a_i \leq 10^9$) — the individual strength of each vampire.

The sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

第一行包含一个整数 $t$（$1 \leq t \leq 10^4$）——测试用例的数量。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 2 \cdot 10^5$）——吸血鬼的数量。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$0 \leq a_i \leq 10^9$）——每个吸血鬼的个体力量值。

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

For each test case, output a single integer — the maximum number of groups among all possible ways to divide the vampires with the smallest sum of strengths.

对于每个测试用例，输出一个整数——在所有将吸血鬼分组的方式中，强度之和最小的前提下，所能得到的最大组数。

In the first test case, the optimal way is to take all the $n$ vampires as a group. So, f(1,3) = 1 \and 2 \and 3 = 0.

In the second test case, the optimal way is to make $2$ groups, $(2,3,1)$ and $(5,2)$. So, f(1,3) + f(4,5) = (2 \and 3 \and 1) + (5 \and 2) = 0 + 0 = 0.

在第一个测试用例中，最优方案是将全部 $n$ 个吸血鬼作为一个组。因此，f(1,3) = 1 \and 2 \and 3 = 0。

在第二个测试用例中，最优方案是划分为 $2$ 个组：$(2,3,1)$ 和 $(5,2)$。因此，f(1,3) + f(4,5) = (2 \and 3 \and 1) + (5 \and 2) = 0 + 0 = 0。