Problem Description

Given a sequence $a$ of length $n$. Define one operation as follows: choose an interval $[l,r]$, let $x=a_l\&a_{l+1}\&\cdots\&a_r$. For any $i$ such that $l \le i \le r$, set $a_i\leftarrow a_i-x$. Ask: what is the minimum number of operations needed to make all numbers in the sequence become $0$?

Here, $\&$ denotes bitwise AND.

Input Format

This problem has multiple test cases.

The first line contains a positive integer $T$, which denotes the number of test cases.

For each test case:

The first line contains a positive integer $n$.

The second line contains $n$ non-negative integers $a_i$.

Output Format

For each test case, output one integer per line, which is the answer.

4
4
1 2 3 1
4
1 2 2 2
4
0 1 1 0
4
1 0 2 4

3
2
1
3

Hint

For $20\%$ of the testdata, it is guaranteed that $1\le T,n\le 8$.

For $40\%$ of the testdata, it is guaranteed that $1\le n\le 500$.

For another $15\%$ of the testdata, it is guaranteed that $a_i\in\{0,1\}$.

For another $15\%$ of the testdata, it is guaranteed that $a_i$ are generated uniformly at random within the value range.

For $100\%$ of the testdata, it is guaranteed that $1\le T\le 50$, $1\le n,\sum n\le 10^5$, $0\le a_i\le 2^{31}-1$.

Translated by ChatGPT 5