#718 XOR 合并

题面

题面语言

给定一个由非负整数构成的长度为 $N$ 的序列 $A=[A_1,A_2,\cdots,A_N]$ 。你希望使序列中的所有元素都相等。

每次操作，你可以选择当前序列中相邻的两个元素 $x,y$ ，将它们合并为一个值为 $x\oplus y$ 的元素，并放在原来的位置。其中， $\oplus$ 表示按位异或运算。每次操作后，序列的长度减少 $1$ ，其余元素的顺序保持不变。

例如，对于序列 $[1,3,2]$ ，合并前两个元素后，由于 $1\oplus3=2$ ，序列会变为 $[2,2]$ 。

求使序列中所有元素都相等所需的最少合并次数。如果所有元素已经相等，答案为 $0$ 。只剩一个元素的序列也视为所有元素都相等。

输入从标准输入按以下格式给出：

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

对于每个测试用例，在一行中输出所需的最少合并次数。

#	分数	数据范围
1	9	$0 \le A_i \le 1$ ( $1 \le i \le N$ ).

样例输入

样例输出

1
2
2

第 1 个测试用例: 合并前两个元素 $1,2$ 后，序列变为 $3,3$ 。

第 2 个测试用例: 合并前两个元素 $1,3$ 后，序列变为 $2,3,1$ 。然后合并最后两个元素，序列变为。