题目描述

小安经过五小时鏖战做出来了一道题，于是他将这道题抛给了你。 他给你一个数组，你需要求数组中有多少个区间L,R，满足区间内所有元素的最大公约数恰好等于它们的异或和。 ​ 以下为一些名词的解释： 在本题中，区间 [l,r] 的最大公约数即 gcd(a~l~,a~$l+1$~,...a~r~)，区间 [l,r] 的异或和即 a~l~ xor a~$l+1$~ xor a~$l+2$~...xor a~r~ gcd⁡，即最大公约数，指两个整数共有约数中最大的一个。例如，$12$ 和 $30$ 的公约数有 $1$,$2$,$3$,$6$ 其中最大的约数是 $6$，因此 gcd($12$,$30$)=$6$。xor表示按位异或运算。

输入格式

每个测试文件均包含多组测试数据。第一行输入一个整数 T($1<=T<=10$^$5$^)代表数据组数，每组测试数据描述如下： 第一行输入一个正整数 $n$ ($1<=n<=2$ $\times$ $10^5$^) 代表数组中的元素数量 第二行输入 $n$ 个整数 a~$1$~,a~$2$~,...a~n~ （$1<=ai <=10$^$9$^） 代表数组中的元素 除此之外，保证单个测试文件的 $n$ 之和不超过 $3$ $\times$ $10^5$^

输出格式

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

样例

样例输入 1

2
5
3 2 6 2 4
3
1 2 3

样例输出 1

3
1

提示

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