题目背景

诗篇已在四风流转中佚失，只有些许残章留下。

巴巴托斯要将这残章收集，而这一节描述的是他与风的力量。

待千风/拂去迷惘，再随那/歌声去/划过穹苍。

题目描述

现在有 \(t\) 章诗篇残章等待整理。

每一篇残章中有 \(n\) 个音符，音符只有 \(α,β,γ\) 三种。

\(γ\) 音符和其它音符相邻的时候音韵是和谐的，但 \(α\) 和 \(β\) 相邻时被认为是不符合音律的。

为了还原亘古时期无暇的乐章，巴巴托斯需要重新排列音符， 使得所有 \(α\) 和 \(β\) 不相邻 。每次移动时 可以将任意一个音符移动到任意位置 。

巴巴托斯想问你最少的移动次数，

并请你喝提瓦特最好的，出自诗人之手的苹果酿。

因为时间磨损了大部分诗篇，可能无法还原成完美的样子，

如果无法排列到目标的话，输出 -1。

输入格式

第一行一个整数 \(t\)，表示待整理的残章数目。

对于每一篇残章：

一行一个整数 \(n\)，表示该篇残章的音符数。

接下来一行 \(n\) 个用空格分割的整数，表示音符的初始排列。

输入时，用 \(0\) 代表 \(α\)，\(1\) 代表 \(β\)，\(2\) 代表 \(γ\) 。

输出格式

\(t\) 行，每行一个整数 \(ans\)，表示最少的移动次数，无解输出 -1。

样例 #1

样例输入 #1

2
5
0 1 0 1 2
9
0 0 0 1 1 2 0 0 2

样例输出 #1

2
1

提示

对于 \(25\%\) 的数据，保证 \(1\leqslant n\leqslant 100\) 。

对于 \(50\%\) 的数据，保证 \(1\leqslant n\leqslant 1000\) 。

对于 \(100\%\) 的数据，保证 \(1\leqslant t\leqslant 500，1\leqslant n\leqslant 5000\) ，且单个数据点中所有 \(n\) 的总和不超过 \(5000\) 。

对于样例#3，满足对 \(25\%\) 数据的约束条件。

对于样例#4，满足对 \(50\%\) 数据的约束条件。

对于样例#5，满足对 \(100\%\) 数据的约束条件。

---

\(我现在会为你歌颂美好的万物万象——\)

\(四季轮转，四风从不止息。\)

\(当然啦，功劳也不是它们的，主要是我的。\)

\(要是没有吟游诗人，谁去把这些传唱？\)