An array b is good if the sum of elements of b is even.

(资料图)

You are given an array a consisting of n positive integers. In one operation, you can select an index i and change ai:=⌊ai2⌋. †

Find the minimum number of operations (possibly 0) needed to make a good. It can be proven that it is always possible to make a good.

† ⌊x⌋ denotes the floor function — the largest integer less than or equal to x. For example, ⌊2.7⌋=2, ⌊π⌋=3 and ⌊5⌋=5.

Input

Each test contains multiple test cases. The first line contains a single integer t (1≤t≤1000) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer n (1≤n≤50) — the length of the array a.

The second line of each test case contains n space-separated integers a1,a2,…,an (1≤ai≤106) — representing the array a.

Do note that the sum of n over all test cases is not bounded.

--------------------------------------------------------------------------------------

中文：

如果 b 的元素之和为偶数，则数组 b 是好的。

给定一个由 n 个正整数组成的数组 a。 在一次操作中，您可以选择索引 i 并更改 ai:=⌊ai/2⌋。

求出完成任务所需的最少操作数（可能为 0）。 可以证明，总是可以制作

好的。

† ⌊x⌋ 表示下取整函数——小于或等于 x 的最大整数。 例如，⌊2.7⌋=2、⌊π⌋=3、⌊5⌋=5。

输入

每个测试包含多个测试用例。 第一行包含一个整数 t (1≤t≤1000) — 测试用例的数量。 测试用例的描述如下。

每个测试用例的第一行包含一个整数 n (1≤n≤50) — 数组 a 的长度。

每个测试用例的第二行包含 n 个空格分隔的整数 a1,a2,…,an (1≤ai≤106) — 表示数组 a。

请注意，所有测试用例的 n 之和是没有界限的。

---------------------------------------------------------------------------

如果和是偶数，那么直接返回0，如果和是奇数，那么去判断每个数字从奇数到偶数，或者从偶数到奇数转化的次数，然后遍历取最小值即可；

下面是代码：（没想到没超时就过了。。。）

关键词：