Description

Alex 有 $N$ 只宠物排成一条直线。这些宠物有3种：猫，狗和狮子。如我们所知，猫和狗不喜欢彼此，但是狮子和这两者都合得来。每次操作，Alex可以把一只宠物移动到另一个位置。Alex希望知道最少需要多少次操作来使得猫和狗不相邻。任务计算出最少需要多少次操作来使得猫和狗不相邻

Input Format

第一行包含一个整数 $T$，表示多组数据的组数。

每组数据包含两行，第一行包含一个整数 $N$，第二行包含 $N$个用空格隔开的数字，表示最初的宠物序列。　$0$ 代表猫，$1$ 代表狗，$2$ 代表狮子。

$1 \leq T \leq 500$

$1 \leq N \leq 5000$

单个测试点的 $N$ 之和不超过 $5000$

Output Format

对于每组测试数据对应输出一行答案。

如果不存在满足要求的方案则输出 -1，否则输出最少需要多少次操作来完成。

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

2
1

样例解释 在第一组测试数据中只需要移动 $2$ 只狗到队列的末尾即可 在第二组测试数据中只需要移动最后一只狮子到第一只狗之前即可