题目描述

小苯拿到了一个数组，他想知道有多少个区间 $[l,r](l \lt r)$ 满足，区间内所有元素的最大公约数恰好等于它们的异或和。

在本题中，区间 $[l,r]$ 的最大公约数即 $\gcd(a_l,a_{l+1},\cdots,a_r)$、区间 $[l,r]$ 的异或和即 $a_l \operatorname{xor}$$a_{l+1} \operatorname{xor}$$\cdots \operatorname{xor} a_r$。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 $T\left(1\leq T\leq 10^5\right)$ 代表数据组数，每组测试数据描述如下：
第一行输入一个正整数 $n \left(1 \leq n \leq 2 \times 10^5\right)$ 代表数组中的元素数量。
第二行输入 $n$ 个正整数 $a_1,a_2,\dots,a_n$$\left(1 \leq a_i \leq 10^9\right)$ 代表数组中的元素。

除此之外，保证单个测试文件的 $n$ 之和不超过 $3 \times 10^5$。

输出描述

对于每一组测试数据，新起一行。输出一个整数，代表满足条件的区间数量。

样例1

输入

2
5
3 2 6 2 4
3
1 2 3

输出

3
1

说明

对于第一组测试数据，一共有三个方案：
取区间 $[1,2]$，区间的异或和以及 $\gcd$ 均等于 $1$；
取区间 $[2,5]$，区间的异或和以及 $\gcd$ 均等于 $2$；
取区间 $[1,5]$，区间的异或和以及 $\gcd$ 均等于 $1$。
对于第二组测试数据，只有一个方案：
取区间 $[2,3]$，区间的异或和以及 $\gcd$ 均等于 $1$。