题目描述

如果一个数组 $a$ 满足所有相邻元素 $a_i$ 和 $a_{i+1}$（$1 \le i < n$）的奇偶性不同，则称该数组是“好”的。注意，长度为 $1$ 的数组显然是“好”的。

现在给定一个长度为 $n$ 的数组。

每次操作，你可以选择任意一对奇偶性相同的相邻元素，将它们删除，并在相同位置插入它们的乘积。

请你求出将数组变为“好”的最少操作次数。

输入格式

输入包含多组测试数据。第一行包含测试用例数 $t$（$1 \le t \le 500$）。接下来是每个测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 100$）。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 10^{9}$）。

输出格式

对于每个测试用例，输出一个整数，表示将数组变为“好”的最少操作次数。

说明/提示

以第一个测试用例为例。选择第 $2$ 个和第 $3$ 个整数，对它们进行操作，数组从 $[1, \color{red}{7}, \color{red}{11}, 2, 13]$ 变为 $[1, \color{red}{77}, 2, 13]$。接着，选择第 $1$ 个和第 $2$ 个整数，数组从 $[\color{red}{1}, \color{red}{77}, 2, 13]$ 变为 $[\color{red}{77}, 2, 13]$。因此需要 $2$ 次操作。可以证明这是最少的操作次数。

在第二个测试用例中，给定的数组已经是“好”的，因此需要 $0$ 次操作。

由 ChatGPT 4.1 翻译

样例

3
5
1 7 11 2 13
4
1 2 3 4
6
1 1 1 2 2 3

2
0
3