1482 - [Balkan2017]Cats

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

第一行包含一个整数T，表示多组数据的组数。 每组数据包含两行，第一行包含一个整数N， 第二行包含N个用空格隔开的数字，表示最初的宠物序列。0代表猫，1代表狗，2代表狮子。 1 <= T <= 500 1 <= N <= 5000 单个测试点的N之和不超过5000

对于每组测试数据对应输出一行答案。 如果不存在满足要求的方案则输出-1，否则输出最少需要多少次操作来完成。