题目内容

给定一个长度为 $n$ 的整数数组 { $a_1,a_2,...,a_n$ }，其中每个元素 $a_i$ 的取值范围为 $0≦a_i≦255$ ；

你需要将该数组划分为若干个互不相交的非空连续子段，这些子段按照在原数组中的顺序排列后，其按位异或 $(xor)$ 结果必须构成一个驼峰序列；

求最多可以划分出多少个这样的子段。

驼峰序列：对于一个序列 { $b_1,b_2,...,b_m$ } 如果其为驼峰序列，那么対于仼意的 $1<i< m$ 都有 $b_{i-1}<b_i>b_{i+1}$ 或者 $b_{i-1}>b_i<b_{i+1}$ 。

输入描述

每个测试文件均包含多组测试数据。

第一行输入一个整数 $t(1≦t≦ 1000)$ ，表示测试用例的组数：

此后 $t$ 组测试数据描述如下：

第一行输入一个整数 $n(1≦n≦2× 10^5)$ ，表示数组长度；

第二行输入 $n$ 个整数 $a_1,a_2,…,a_n(0≦a_i≦255)$ ，表示数组元素；

除此之外，保证所有测试用例的 $n$ 之和不超过 $2×10^5$ 。

对于每组测试数据，输出一个整数，表示最大可划分出的满足条件的子段数量。

输入

3
6
1 2 3 0 1 3
4
0 0 0 0
1
85

输出

3
2
1

说明

在第一组数据中，数组 { $1,2,3,0,1,3$ } 可以划分为 { $1$ },{ $2$ },{ $3,0,1,3$ }，按位异或结果为 $1,2,1$ ，是驼峰序列。

在第二组数据中，数组 { $0,0,0,0$ } 可以划分为 { $0,0$ },{ $0,0$ } ，对于任意的 $1<i< m$ 均满足条件(因为找不到满足 $1<i<m$ 的 $i$ ) 。