题目描述

给定一个整数数组 $a$，现在我们希望 $a$ 数组整数之和为 偶数。

在一次操作中，你可以选择 $a_i$，并且将 $a_i$更新为 $[\frac{a_i}{2}]$ (整除2)。

现在请你求解，至少需要操作多少次可以让整数之和为偶数？

数据范围

对于 $100$%的数据：$1≤T≤10^3,1≤n≤50,1≤a_i≤10^6$。

输入格式

输入的第一行包含一个整数 $T$ ，表示数据组数。

接下来 $T$ 组数据，在每组数据当中，先读入一个整数 $n$，表示数组长度。

每组数据的第二行包含 $n$ 个整数 $a_i$，每个整数。

输出格式

输出 $T$ 行，对于每组数据，输出完成题目要求所需的最小操作次数。

4
4
1 1 1 1
2
7 4
3
1 2 4
1
15

0
2
1
4

提示

样例数据解释：

在第一个测试用例中，序列之和已经为偶数，无需操作。

在第二个测试用例中，可以对 $a_2$ 操作两次，$[7,4]->[7,2]->[7,1]$。

在第三个测试用例中，可以对 $a_1$ 操作一次，$[1,2,4]->[0,2,4]$，或者对 $a_2$ 操作一次，$[1,2,4]->[1,1,4]$。