#P1482. [Balkan2017]Cats

[Balkan2017]Cats

当前没有测试数据。

Description

Alex 有N只宠物排成一条直线。这些宠物有3种:猫,狗和狮子。如我们所知,猫和狗不喜欢彼此,但是狮子和这

两者都合得来。每次操作,Alex可以把一只宠物移动到另一个位置。Alex希望知道最少需要多少次操作来使得猫和

狗不相邻。任务计算出最少需要多少次操作来使得猫和狗不相邻

Input

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

每组数据包含两行,第一行包含一个整数N,

第二行包含N个用空格隔开的数字,表示最初的宠物序列。0代表猫,1代表狗,2代表狮子。

1 <= T <= 500

1 <= N <= 5000

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

Output

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

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

Samples

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