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 的元素之和為偶數(shù)，則數(shù)組 b 是好的。

給定一個(gè)由 n 個(gè)正整數(shù)組成的數(shù)組 a。 在一次操作中，您可以選擇索引 i 并更改 ai:=?ai/2?。

求出完成任務(wù)所需的最少操作數(shù)（可能為 0）。 可以證明，總是可以制作

? 好的。

? ?x? 表示下取整函數(shù)——小于或等于 x 的最大整數(shù)。 例如，?2.7?=2、?π?=3、?5?=5。

輸入

每個(gè)測(cè)試包含多個(gè)測(cè)試用例。 第一行包含一個(gè)整數(shù) t (1≤t≤1000) — 測(cè)試用例的數(shù)量。 測(cè)試用例的描述如下。

每個(gè)測(cè)試用例的第一行包含一個(gè)整數(shù) n (1≤n≤50) — 數(shù)組 a 的長(zhǎng)度。

每個(gè)測(cè)試用例的第二行包含 n 個(gè)空格分隔的整數(shù) a1,a2,…,an (1≤ai≤106) — 表示數(shù)組 a。

請(qǐng)注意，所有測(cè)試用例的 n 之和是沒(méi)有界限的。

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

如果和是偶數(shù)，那么直接返回0，如果和是奇數(shù)，那么去判斷每個(gè)數(shù)字從奇數(shù)到偶數(shù)，或者從偶數(shù)到奇數(shù)轉(zhuǎn)化的次數(shù)，然后遍歷取最小值即可；

下面是代碼：（沒(méi)想到?jīng)]超時(shí)就過(guò)了。。。）