#718 XOR Merge

Statement

Statement language

You are given a sequence $A=[A_1,A_2,\cdots,A_N]$ of $N$ nonnegative integers. You want to make all elements of the sequence equal.

In one operation, you may choose two adjacent elements $x,y$ in the current sequence and replace them with the single element $x\oplus y$ , where $\oplus$ denotes bitwise XOR. This merge reduces the length of the sequence by $1$ and leaves the order of all other elements unchanged.

For example, merging the first two elements of $[1,3,2]$ produces $[2,2]$ , because $1\oplus3=2$ .

Find the minimum number of merges needed to make all elements of the sequence equal. If they are already equal, the answer is $0$ . A sequence with only one element also satisfies this condition.

Input

The input is given from Standard Input in the following format:

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$

Output

For each test case, print the minimum number of merges needed, on a separate line.

Constraints

$1 \le T \le 300\,000$ .
$1 \le N \le 300\,000$ .
$0 \leq_{}$ ().

Subtasks

#	Score	Constraints
1	9	$0 \le A_i \le 1$ ( $1 \le i \le N$ ).

Samples

Input

Output

1
2
2

First test case: Merging the first two elements $1,2$ changes the sequence to $3,3$ .

Second test case: Merging the first two elements $1,3$ changes the sequence to $2,3,1$ . Then merging the last two elements makes the sequence .