#718 XOR 併合

問題文

問題文の言語

非負整数からなる長さ $N$ の数列 $A=[A_1,A_2,\cdots,A_N]$ が与えられる。この数列のすべての要素を同じ値にしたい。

1 回の操作では、現在の数列で隣り合う 2 つの要素 $x,y$ を選び、それらを $x\oplus y$ という 1 つの要素に置き換えることができる。ここで、 $\oplus$ はビットごとの XOR 演算を表す。この操作によって数列の長さは $1$ 減り、ほかの要素の順序は変わらない。

例えば、数列 $[1,3,2]$ の先頭の 2 要素を併合すると、 $1\oplus3=2$ なので、数列は $[2,2]$ になる。

数列のすべての要素を同じ値にするために必要な併合回数の最小値を求めよ。最初からすべての要素が等しい場合、答えは $0$ である。また、要素が 1 つだけの数列も、すべての要素が等しいものとする。

入力は標準入力から次の形式で与えられる。

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$

各テストケースについて、必要な併合回数の最小値を 1 行に出力せよ。

#	得点	制約
1	9	$0 \le A_i \le 1$ ( $1 \le i \le N$ ).

入力例

出力例

1
2
2

1 番目のテストケース: 先頭の 2 要素 $1,2$ を併合すると、数列は $3,3$ になる。

2 番目のテストケース: 先頭の 2 要素 $1,3$ を併合すると、数列は $2,3,1$ になる。その後、末尾の 2 要素を併合すると、数列はになる。