Happy Residents

Ninja town has ‘N’ houses along a street. The houses are either painted red or blue. The house colours are given in an integer array ‘color’, where 0 denotes the ith house is painted red, and 1 denotes the ith house is painted blue. The residents of a house will be happy if their house colour is different from both its neighbours if they exist. Hence, the Mayor decided to repaint some of the houses. But due to financial reasons, he wants to paint a minimum number of houses. Can you calculate the minimum number of houses that he needs to repaint?

Example: Suppose there are 3 houses and the colours [1, 1, 1], which means all the houses are coloured blue. If the Mayor repaints the second house to red, we will have the colours as [1, 0, 1]. We can see that all the neighbours will be happy. Hence, the minimum number of houses to be repainted is 1.

Input Format:

The first line contains ‘T’, denoting the number of test cases.

The first line of each test case contains two integers, ‘N’ denoting the number of houses.

The second line of each test case contains an array ‘color’ containing ‘N’ space-separated integers.

Output Format:

For each test case, print a single integer, denoting the minimum number of houses that need to be repainted.

Note:

You are not required to print the expected output. It has already been taken care of. Just implement the function.

Constraints:

1 <= T <= 10
1 <= N <= 10^5
0 <= color[i] <= 1

Time Limit: 1 sec