乔纳森正在对抗 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$$$。