Hair Tying

Sihyeon likes changing and tying up people's hairstyles. A hairstyle is one of $0$ (straight hair), $1$ (ponytail), $2$ (pigtails), or $3$ (three-strand braid).

Given hairstyles $A_1, A_2, \cdots, A_N$, Sihyeon can pick $l$ and $r$ and set the hairstyles of people $l$ through $r$ all at once to $A_l \oplus A_{l+1} \oplus \cdots \oplus A_r$. $\oplus$ is the bitwise XOR operator.

Sihyeon dislikes the oddly shaped three-strand braid, so Sihyeon wants to make sure nobody has a three-strand braid. Find the minimum number of hairstyle changes.

The input has several test cases. The first line contains the number of test cases $T$. ($1 \le T \le 20\,000$)

The first line of each test case gives $N$. ($1 \leq N \leq 10^6$)

The second line gives the $N$ hairstyles $A_1, A_2, \cdots, A_N$, separated by spaces. ($0 \leq A_i \leq 3$)

The sum of $N$ over all test cases does not exceed $10^6$.

For each test case, print on one line the minimum number of hairstyle changes needed so that no three-strand braid remains. If a three-strand braid remains no matter how you change the hairstyles, print $-1$.