XOR 병합

음이 아닌 정수로 이루어진 길이 $N$의 수열 $A=[A_1,A_2,\cdots,A_N]$이 주어진다. 이 수열의 모든 원소를 같은 값으로 만들려고 한다.

한 번의 연산으로 현재 수열에서 서로 인접한 두 원소 $x,y$를 골라, 그 자리에 $x\oplus y$ 하나만 남기도록 합칠 수 있다. 여기서 $\oplus$는 비트 XOR 연산이다. 이 연산을 수행하면 수열의 길이가 $1$ 줄어들며, 나머지 원소의 순서는 바뀌지 않는다.

예를 들어, 수열 $[1,3,2]$에서 앞의 두 원소를 합치면 $1\oplus3=2$이므로 수열은 $[2,2]$가 된다.

수열의 모든 원소를 같은 값으로 만드는 데 필요한 병합 횟수의 최솟값을 구하여라. 이미 모든 원소가 같다면 답은 $0$이며, 원소가 하나만 남은 수열도 모든 원소가 같은 것으로 본다.

입력은 다음과 같은 형식으로 주어진다.

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

각 테스트 케이스마다 필요한 최소 병합 횟수를 한 줄에 하나씩 출력한다.

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