题目描述

给定一个长度为 $n$ 的非负整数序列 $a$，你可以进行若干次下列操作（可以不进行操作）：

1. 选择两个正整数 $p,x$，其中 $1\le p\le n$。
2. 对于所有 $1\le i\le p$，将 $a_i$ 修改为 $a_i\oplus x$，其中 $\oplus$ 表示按位异或运算。

求最少要多少次操作，才能使序列 $a$ 单调不降。可以证明总是存在这样的方案。

输入格式

本题输入量较大，请注意选择较快的输入方式。

本题包含多组测试数据。

输入的第一行包含一个非负整数 $c$ 和一个正整数 $t$，分别表示测试点编号与测试数据组数。$c=0$ 表示该测试点为样例。

接下来依次输入每组测试数据，对于每组测试数据：

• 第一行包含一个正整数 $n$，代表序列的长度；
• 第二行包含 $n$ 个非负整数 $a_1, a_2, \ldots, a_n$。

输出格式

对于每组测试数据，输出一行一个非负整数，表示使序列 $a$ 单调不降所需的最少操作次数。

0 5
5
4 5 0 7 3
5
7 4 6 0 4
3
0 0 7
10
9 1 5 5 5 12 12 14 15 15
10
7 2 11 10 15 0 12 14 2 6

2
2
0
1
3

提示

【样例 1 解释】

对于第一组测试数据，初始序列 $a$ 为 $[4,5,0,7,3]$，一种达到最小次数的方案是：

• 进行操作 $p=3,x=8$，此时 $a=[12,13,8,7,3]$。
• 然后进行操作 $p=5,x=12$，此时 $a=[0,1,4,11,15]$。

此时 $a$ 单调不降。操作次数为 $2$，可以证明没有操作次数更少的方案。

对于第二组测试数据，初始序列 $a$ 为 $[7,4,6,0,4]$，一种达到最小次数的方案是：

• 进行操作 $p=2,x=2$，此时 $a=[5,6,6,0,4]$。
• 然后进行操作 $p=4,x=4$，此时 $a=[1,2,2,4,4]$。

操作次数为 $2$，可以证明没有操作次数更少的方案。

【样例 2】

见选手目录下的 rain/rain2.in 与 rain/rain2.ans。

该样例满足测试点 $1$ 的条件限制。

【样例 3】

见选手目录下的 rain/rain3.in 与 rain/rain3.ans。

该样例满足测试点 $2\sim3$ 的条件限制。

【样例 4】

见选手目录下的 rain/rain4.in 与 rain/rain4.ans。

该样例满足测试点 $9\sim10$ 的条件限制。

【样例 5】

见选手目录下的 rain/rain5.in 与 rain/rain5.ans。

该样例满足测试点 $15\sim 17$ 的条件限制。

【样例 6】

见选手目录下的 rain/rain6.in 与 rain/rain6.ans。

该样例满足测试点 $18\sim 22$ 的条件限制。

【样例 7】

见选手目录下的 rain/rain7.in 与 rain/rain7.ans。

该样例满足测试点 $23$ 的条件限制。

【样例 8】

见选手目录下的 rain/rain8.in 与 rain/rain8.ans。

该样例满足测试点 $24\sim 27$ 的条件限制。

【样例 9】

见选手目录下的 rain/rain9.in 与 rain/rain9.ans。

该样例满足测试点 $29\sim 33$ 的条件限制。

【样例 10】

见选手目录下的 rain/rain10.in 与 rain/rain10.ans。

该样例满足测试点 $36\sim 41$ 的条件限制。

【样例 11】

见选手目录下的 rain/rain11.in 与 rain/rain11.ans。

该样例满足测试点 $45\sim 50$ 的条件限制。

【数据范围】

设 $N$ 表示单个测试点内所有 $n$ 的和，$V$ 表示单个测试点内所有 $a_i$ 的最大值。对于所有测试数据，保证：

• $1\le t\le 100$；
• $1\le n\le 10^6$，$1\le N\le 5\times 10^6$；
• 对于所有 $1\le i\le n$，均有 $0\le a_i<2^{30}$。

测试点编号	$n\le$	$N\le$	$V<$	特殊性质
$1$	$3$	$100$	$2^{10}$	×
$2\sim3$	$4$	^	^	^
$4\sim5$	$3$		$2^{30}$
$6\sim 8$	$4$		^
$9\sim10$	$10$
$11\sim 14$	$17$
$15\sim 17$	$400$	$2\,000$	$2^{10}$
$18\sim 22$	$5\,000$	$3\times 10^4$	^
$23$	$2\,000$	$10^4$	$2^{30}$	$\checkmark$
$24\sim 27$	^		^	×
$28$	$5\,000$	$3\times 10^4$		$\checkmark$
$29\sim 33$	^			×
$34\sim35$	$10^5$	$7\times 10^5$		$\checkmark$
$36\sim 41$	^			×
$42\sim 44$	$10^6$	$5\times 10^6$		$\checkmark$
$45\sim 50$	^			×

特殊性质：$a_n=0$。