说明

Miaowu要用四种涂料（红、黄、蓝、绿）将一块1*n的n个格子涂色，但是他特别讨厌涂色，所以他就把四种涂料随意往区域上倒，当他倒完的时候，发现运气很好，每一个格子都只有一种颜色，当他正在欣赏这个杰作时，突然想起一个要求：要求相邻的两个格子不能是同样的颜色！

这让他很苦恼，因为他随意往区域上泼所以导致很多相邻的格子都是相同的颜色，现在他需要用其他颜色把一些不符合规则的格子覆盖上去，由于他很懒，所以，需要你帮他算出，最少需要修改几个格子的颜色才能使得相邻的格子不是同一种颜色。

输入格式

第一行输入一个数T，表示测试数据个数，对于每组测试数据，第一行输入一个n(0<n<=10^6)，表示有n个格子，然后第二行输入n个数，每个数只可能是1(代表红色)、2(代表黄色)、3(代表蓝色)、4(代表绿色)。

输出格式

对于每组数据，输出一个值，表示最少需要重新涂多少个格子才能使得相邻两个格子不是同样的颜色。

样例

3
6
1 1 1 1 1 1
7
4 4 4 4 4 4 4
9
1 2 3 4 3 2 1 2 3

3
3
0

提示

不要用cin和cout，以免超时哦~

用scanf和printf吧~