You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

我们认为奇偶相间的序列是好的序列

题目描述

给你一个序列, 你需要将它变成一个好序列, 我们可以通过以下方式.

如果相邻两个元素奇偶性相同, 则将两数合并, 合并后的结果为两数的乘积, 问需要多少次操作才可以合并为一个好序列呢?

数据格式

输入格式

第一行输入一个整数 $t$, 表示有 $t$ 组数据.

接下来每组数据, 第一行输入一个整数 $n$, 表示元素的个数, 接下来一行 $n$ 个整数, 表示修改之前的序列.

输出格式

输出 $t$ 行, 每行一个整数表示最少需要操作的次数

样例

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

3
2
3

样例解释

2 6 2 5 7 经过 $3$ 次修改后变为 24 35

数据范围

$1 <= t <= 20$

$1 <= |s| <= 1000$