A15983 | 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 <a href="https://en.wikipedia.org/wiki/Bitwise_operation#AND">bitwise AND operation</a>. </p><p>Because Jonathan would like to defeat the vampire minions fast, he will divide the vampires into contiguous groups, such that each vampire is in <span class="tex-font-style-bf">exactly</span> one group, and the <span class="tex-font-style-bf">sum</span> of <span class="tex-font-style-it">strengths</span> of the groups is <span class="tex-font-style-bf">minimized</span>. Among all ways to divide the vampires, he would like to find the way with the <span class="tex-font-style-bf">maximum</span> number of groups.</p><p>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.

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

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.