A. Beat The Odds

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Given a sequence a1,a2,…,ana1,a2,…,an, find the minimum number of elements to remove from the sequence such that after the removal, the sum of every 22 consecutive elements is even.

Input

Each test contains multiple test cases. The first line contains a single integer tt (1≤t≤1001≤t≤100) — the number of test cases. Description of the test cases follows.

The first line of each test case contains a single integer nn (3≤n≤1053≤n≤105).

The second line of each test case contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤1091≤ai≤109) — elements of the sequence.

It is guaranteed that the sum of nn over all test cases does not exceed 105105.

Output

For each test case, print a single integer — the minimum number of elements to remove from the sequence such that the sum of every 22 consecutive elements is even.

Example

input

Copy

2
5
2 4 3 6 8
6
3 5 9 7 1 3

output

Copy

1
0

Note

In the first test case, after removing 33, the sequence becomes [2,4,6,8][2,4,6,8]. The pairs of consecutive elements are {[2,4],[4,6],[6,8]}{[2,4],[4,6],[6,8]}. Each consecutive pair has an even sum now. Hence, we only need to remove 11 element to satisfy the condition asked.

In the second test case, each consecutive pair already has an even sum so we need not remove any element.

Problem solving instructions ： Water problem , Or delete all the odd numbers 、 Or delete all even numbers .

#include"stdio.h"
#include"math.h"

int main()
{
	int k, b, x;
	scanf("%d", &k);
	for (int i = 0; i<k; i++)
	{
		int br = 0;
		scanf("%d", &b);
		for (int j = 0; j<b; j++)
		{
			scanf("%d", &x);
			if (x % 2 != 0)
			{
				br++;
			}
		}
		if (br > b - br)
		{
			printf("%d\n", b - br);
		}
		else
		{
			printf("%d\n", br);
		}
	}
	return 0;

}