题目描述

大魔王林克要给波克布林们发食物了！ 为了保证秩序，波克布林们需要排队来领取食物，同时，每个波克布林都有一个自己的ID。但是大魔王肯定是有自己的独特癖好的，大魔王想让排队的队列中，任意两个相邻的波克布林的ID之和均为偶数。 若要满足这个条件，请你计算最少的需要移出队列的波克布林的数目。

输入格式

有多组数据

第一行包括一个整数$t$($1 \le t \le 100$),表示有$t$组数据

每组数据的第一行包括一个整数$n$（$3 \le n \le 10^5$)

每组数据的第二行包括$n$个整数$a_{1}$,$a_{2}$,...,$a_{n}$($1 \le a_{1} \le 10^9$)

保证$n$在所有数据里不超过$10^5$

输出格式

输出$t$行，表示最少的需要移出队列的波克布林的数目。

2

5

2 4 3 6 8

6

3 5 9 7 1 3

1
0

提示

输入输出样例说明： 在第一组数据中，删除3后序列变成[2、4、6、8],满足题目要求，因此只需删除一个元素即可，输出1 在第二组数据中，每两个连续数的和都是偶数，因此不需要删除任何元素，输出0