该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给定一个长度为 $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}$。

特殊性质：$a_n=0$。