← 返回题目列表

Codeforces · 1847/B

B. 哈蒙奥德赛

中文机器翻译题面 查看原题

乔纳森正在对抗 DIO 的吸血鬼爪牙。其中有 $$$n$$$,其优势为 $$$a_1、a_2、\dots、a_n$$$。 $$$\def\and {{\,\texttt{&}\,}}$$$

将 $$$(l, r)$$$ 表示为由索引从 $$$l$$$ 到 $$$r$$$ 的吸血鬼组成的组。乔纳森意识到任何此类组的力量都在于其最薄弱的环节,即按位与。更正式地,组 $$$(l, r)$$$ 的强度级别定义为 $$$$$$f(l,r) = a_l \and a_{l+1} \and a_{l+2} \and \ldots \and a_r。$$$$$$ 这里,$$$\and$$$ 表示按位 AND 运算。

因为乔纳森想快速击败吸血鬼爪牙,他会将吸血鬼分成连续的组,这样每个吸血鬼都恰好在一个组中,并且组的力量总和最小。在所有划分吸血鬼的方法中,他想找到群体数量最多的方法。

给定每个 $$$n$$$ 吸血鬼的优势,在所有可能的方法中找到最大的组数,以最小的优势来划分吸血鬼。

输入

第一行包含一个整数 $$$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$$$。

输出

对于每个测试用例,输出一个整数——以最小的力量总和来划分吸血鬼的所有可能方法中的最大组数。

示例

输入 #1

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

输出 #1

1
2
1

注意

在第一个测试用例中,最佳方法是将所有 $$$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$$$。