从后往前做异或和,每次让第i个元素和后面的所有元素相等,后面处理过的元素是不会再改变了,前面累计异或的值可以用一个值来维护。
如果当前元素和累计异或值异或之后还是不等于最后一个元素,就将答案加一。
小红有一个长度为n的数组{a1,a2,...,an},他希望将a的所有值全变成相同的,为此他可以做如下操作:
任选两个整数i,x(1≤i≤n),(0≤x≤109),将i的前缀的每个值都异或上x,即对所有的j(1≤j≤i)都执行:aj=xorx。
小红想知道最少几次操作可以将a数组所有数字变为相同的。
每个测试文件均包含多组测试数据。第一行输入一个整数T(1≤T≤1000)代表数据组数,每组测试数据描述如下:
第一行输入一个整数n(1≤n≤2×105)代表数组中的元素数量。
第二行输入n个整数a1,a2,...,an(1≤ai≤108)代表数组元素。
(保证每个测试文件的数据中,n的总和不超过200000。)
对于每一组测试数据,在一行上输出一个整数,代表最少的操作次数。
输入
2
4
1 1 2 2
5
1 2 3 4 5
输出
1
4
说明
对于第一组测试数据,选择i=2且x=3,随后执行一次操作,数组变为{1xor3,1xor3,2,2}。