P17332 "TPOI-2B" AND and Subsequence

磨棱刓角。

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](https://baike.baidu.com/item/&/16825228?fromtitle=%E6%8C%89%E4%BD%8D%E4%B8%8E&fromid=9601818).

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

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

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