解题思路

关键性质

• 合并相邻两个数，用它们的乘积替换。乘积的奇偶只由因子决定：

  • 只要其中一个是偶数，乘积就是偶数；
  • 两个都是奇数，乘积才是奇数。

• 因而：

题目内容

给定一个长度为 $n$ 的整数数组 {$a_1,a_2,...,a_n$}；

由于 Tk 的 强追症，他不希望数组中同时存在奇数和偶数。为了满足条件，可以对数组执行以下操作，一次操作描述为：

• 选择两个相邻元素 $a_i$ 和 $a_{i+1}$ ，将它们从数组中删除，并在原位置插入它们的乘积 $a_i × a_{i+1}$ 。

求解，使数组仅包含奇数或仅包含偶数，所需的最少操作次数。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 $T(1 ≦T ≦ 10^4)$ ，表示数据组数;此后每组测试数据格式如下：

第一行输入一个整数 $n(1≦n≦2×10^5)$ ，表示数组的长度；

第二行输入 $n$ 个整数 $a_1,a_2,...,a_n(1 ≦a_i≦ 10^9)$ 表示数组元素。

除此之外，保证单个测试文件的 $n$ 之和不超过 $2×10^5$ 。

输出描述

对于每组测试数据，新一行输计一个整数，表示使数组仅包含奇数或仅包含偶数所需的最少操作次数。

样例1

输入

2
2
1 2
3
2 3 2

输出

1
1

说明

在第一个样例中，$n=2$ ，数组 {$1,2$ }；对这两个元素进行一次操作，得到 $1×2=2$ ，数组变为 {$2$}，仅含偶数，故答案为 $1$ 。

在第二个样例中，$n= 3$ ，数组 {$2,3,2$ }；只需一次操作如合并后两个元素 $3$ 和 $2$ 得到 $6$ ，数组变为 {$2,6$}，仅含偶数，故答案为 $1$ 。