30910번 - 머리 묶기

시현이는 사람들의 헤어 스타일을 바꾸어 묶는 것을 좋아한다. 사람들의 헤어 스타일에는 $0$ (생머리), $1$ (포니테일), $2$ (양갈래), $3$ (세갈래)이 있다.

시현이는 사람들의 헤어스타일 $A_1, A_2, \cdots, A_N$이 있을 때, $l$과 $r$을 적절히 골라 $l$번째부터 $r$번째까지 사람의 헤어 스타일을 동시에 $A_l \oplus A_{l+1} \oplus \cdots \oplus A_r$로 바꿀 수 있다. $\oplus$는 Bitwise XOR 연산자이다.

시현이는 모양이 이상한 세갈래를 싫어해서, 어떤 사람의 헤어 스타일도 세갈래가 아니도록 만들려고 한다. 사람들의 헤어 스타일을 바꾸는 최소 횟수를 구해 보자.

입력은 여러 개의 테스트케이스로 이루어져 있다. 입력의 첫째 줄에는 테스트케이스의 수 $T$가 주어진다. ($1 \le T \le 20\,000$)

각 테스트케이스의 첫째 줄에는 $N$이 주어진다. ($1 \leq N \leq 10^6$)

둘째 줄에는 $N$명의 헤어 스타일 $A_1, A_2, \cdots, A_N$이 공백으로 구분되어 주어진다. ($0 \leq A_i \leq 3$)

모든 테스트케이스의 $N$의 합은 $10^6$을 초과하지 않는다.

각 테스트케이스마다 한 줄에, 세갈래가 없도록 할 수 있다면 헤어 스타일을 바꾸는 최소 횟수를, 어떻게 바꾸어도 세갈래가 남는다면 $-1$을 출력한다.