为了训练小 Kevin 的算术技能，他的母亲设计了以下问题。

给定 $n$ 个整数 $a_1, a_2, \dots, a_n$ 和一个初始为 $0$ 的和 $s$，Kevin 按顺序对 $i = 1, 2, \dots, n$ 执行以下操作：

• 将 $a_i$ 加到 $s$ 上。如果结果 $s$ 是偶数，Kevin 获得一分，并将 $s$ 反复除以 $2$，直到它变为奇数。

注意，无论 Kevin 执行了多少次除法，每次操作最多只能获得一分。

由于这些除法被认为对 Kevin 的发展更有益，他的母亲希望重新排列 $a$，使得 Kevin 获得的总分最大化。请确定最大得分。

输入格式

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$ ($1 \le t \le 500$)。 接下来是测试用例的描述。 每个测试用例的第一行包含一个整数 $n$ ($1 \le n \le 100$) —— 整数的个数。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$)。

输出格式

对于每个测试用例，输出一个整数 —— 最大得分。

样例

输入 1

5
1
1
2
1 2
3
2 4 6
4
1000000000 999999999 999999998 999999997
10
3 1 4 1 5 9 2 6 5 3

输出 1

0
2
1
3
8

说明

在第一个测试用例中，$a$ 的唯一排列是 $[1]$。$s$ 变为 $1$。Kevin 没有得分。 在第二个测试用例中，$a$ 的唯一可能排列是 $[2, 1]$。$s$ 依次变为 $1$ 和 $1$。Kevin 在两次操作中都获得了分数。 在第三个测试用例中，$a$ 的一种可能排列是 $[2, 4, 6]$。$s$ 依次变为 $1, 5, 11$。Kevin 在第一次操作中获得了一分。