题目内容

小塔有一个长度为$n$的数组{$a_1,a_2,...,a_n$},他希望将$a$的所有值全变成相同的，为此他可以做如下操作：

• 任选两个整数$i$，$x$($1≤i≤n$),($0≤x≤10^9$),将$i$的前缀的每个值都异或上$x$，即对所有的$j$（$1≤j≤i$）都执行：$a_j=xorx$。

  小塔想知道最少几次操作可以将$a$数组所有数字变为相同的。

输入描述

​ 每个测试文件均包含多组测试数据。第一行输入一个整数$T$（$1≤T≤1000$）代表数据组数，每组测试数据描述如下：

​ 第一行输入一个整数$n$($1≤n≤2×10^5$)代表数组中的元素数量。

​ 第二行输入$n$个整数$a_1,a_2,...,a_n$($1≤a_i≤10^8$)代表数组元素。

（保证每个测试文件的数据中，$n$的总和不超过$200000$。）

输出描述

对于每一组测试数据，在一行上输出一个整数，代表最少的操作次数。

样例1

输入

2
4
1 1 2 2
5 
1 2 3 4 5

输出

1
4

说明

对于第一组测试数据，选择$i=2$且$x=3$,随后执行一次操作，数组变为{$1xor3,1xor3,2,2$}。