머리 묶기

시현이는 사람들의 헤어 스타일을 바꾸어 묶는 것을 좋아한다. 헤어 스타일은 $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$는 비트 단위 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$을 출력한다.