310530: CF1847B. Hamon Odyssey

B. Hamon Odysseytime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

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.

Input

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$.

Output

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.

ExampleInput

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

Output

1
2
1

Note

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$.

题目大意：
这个题目是关于将吸血鬼分成不同的小组，每个小组的力量由组内所有吸血鬼力量的按位与（bitwise AND）决定。目标是将吸血鬼分成尽可能多的小组，同时使得所有小组力量的总和最小。要求输出最大数量的小组。

输入输出数据格式：
输入：
- 第一行包含一个整数 t（1 ≤ t ≤ 10^4），表示测试用例的数量。
- 每个测试用例的描述如下：
- 第一行包含一个整数 n（1 ≤ n ≤ 2 × 10^5），表示吸血鬼的数量。
- 第二行包含 n 个整数 a_1, a_2, ..., a_n（0 ≤ a_i ≤ 10^9），表示每个吸血鬼的力量。
- 所有测试用例的 n 之和不超过 2 × 10^5。

输出：
- 对于每个测试用例，输出一个整数，表示在所有可能的分组方式中，小组数量最大的情况下的最小力量总和的小组数量。

示例：
输入：
```
3
3
1 2 3
5
2 3 1 5 2
4
5 7 12 6
```
输出：
```
1
2
1
```

注意：
- 在第一个测试用例中，最优的方式是将所有 n 个吸血鬼作为一个小组，因此 f(1,3) = 1 & 2 & 3 = 0。
- 在第二个测试用例中，最优的方式是分为 2 个小组，(2,3,1) 和 (5,2)。因此，f(1,3) + f(4,5) = (2 & 3 & 1) + (5 & 2) = 0 + 0 = 0。题目大意： 这个题目是关于将吸血鬼分成不同的小组，每个小组的力量由组内所有吸血鬼力量的按位与（bitwise AND）决定。目标是将吸血鬼分成尽可能多的小组，同时使得所有小组力量的总和最小。要求输出最大数量的小组。 输入输出数据格式： 输入： - 第一行包含一个整数 t（1 ≤ t ≤ 10^4），表示测试用例的数量。 - 每个测试用例的描述如下： - 第一行包含一个整数 n（1 ≤ n ≤ 2 × 10^5），表示吸血鬼的数量。 - 第二行包含 n 个整数 a_1, a_2, ..., a_n（0 ≤ a_i ≤ 10^9），表示每个吸血鬼的力量。 - 所有测试用例的 n 之和不超过 2 × 10^5。 输出： - 对于每个测试用例，输出一个整数，表示在所有可能的分组方式中，小组数量最大的情况下的最小力量总和的小组数量。 示例： 输入： ``` 3 3 1 2 3 5 2 3 1 5 2 4 5 7 12 6 ``` 输出： ``` 1 2 1 ``` 注意： - 在第一个测试用例中，最优的方式是将所有 n 个吸血鬼作为一个小组，因此 f(1,3) = 1 & 2 & 3 = 0。 - 在第二个测试用例中，最优的方式是分为 2 个小组，(2,3,1) 和 (5,2)。因此，f(1,3) + f(4,5) = (2 & 3 & 1) + (5 & 2) = 0 + 0 = 0。