고양이

알렉스는 반려동물 $N$마리를 한 줄로 세워 두었다. 동물은 고양이, 개, 사자 세 종류다. 고양이와 개는 사이가 나쁘지만, 사자는 고양이와도 개와도 잘 지낸다.

알렉스는 이동을 한 번 할 때마다 동물 한 마리를 골라 줄의 다른 자리로 옮길 수 있다.

고양이와 개가 서로 이웃하지 않도록 줄을 바꾸려고 한다. 필요한 최소 이동 횟수를 구하는 프로그램을 작성하시오.

첫째 줄에 서로 독립인 테스트 케이스의 수 $T$가 주어진다.

각 테스트 케이스는 두 줄로 이루어진다. 첫째 줄에 정수 $N$이 주어진다. 둘째 줄에는 줄에 선 순서대로 동물 $N$마리의 종류가 공백으로 구분되어 주어진다. 고양이는 0, 개는 1, 사자는 2로 나타낸다.

각 테스트 케이스마다 한 줄씩 출력한다. 고양이와 개가 이웃하지 않도록 배치할 방법이 없으면 -1을 출력하고, 그렇지 않으면 필요한 최소 이동 횟수를 출력한다.

• $1 \le T \le 500$
• $1 \le N \le 5000$
• 한 입력에 주어지는 모든 $N$의 합은 5000 이하다.

첫 번째 예제의 첫 테스트에서는 개 두 마리를 줄의 끝으로 옮긴다. 두 번째 테스트에서는 마지막 사자를 첫 번째 개 앞으로 옮긴다.