题目描述

她擅长多种魔法，而且致力于开发新魔法。——《东方求闻史纪》

帕秋莉正在制作一个魔法护身符。她现在有 $n$ 个魔法令牌，令牌上的魔力值可以用正整数数列 $a_1,a_2,\dots,a_n$ 来表示。
帕秋莉可以对她的魔法令牌进行如下两种操作。

• 融合：帕秋莉可以选择两块令牌并且将它们移除，并且创造出一块新的令牌，其魔力值为这两块令牌的魔力值的和。
• 降低：帕秋莉可以选择一个魔力值为一个偶数 $x$ 的令牌，将其移除，创造出一块新的令牌，其魔力值变为 $\dfrac{x}{2}$。

由于当魔力值为奇数的时候这些令牌的工作效率会达到最高，所以请你帮助帕秋莉，告诉她把这些令牌的魔力值都变成奇数，所需的最小次数是多少。

输入格式

第一行输入一个正整数 $t(1 \leq t \leq 10^3)$，表示输入数据组数。
对于每组数据，第一行输入一个正整数 $n(1 \leq n \leq 2\times 10^5)$，表示魔法令牌的个数。
第二行输入 $n$ 个正整数 $a_i(1 \leq a_i \leq 10^9)$，表示魔法令牌上的魔力值。
数据保证，对于每组数据，$\sum n \leq 2 \times 10^5$。

输出格式

对于每一组数据，输出一个正整数，表示把这些令牌的魔力值都变成奇数，所需的最小次数是多少。可以证明一定存在一种方式。

样例

4
2
1 9
3
1 1 2
3
2 4 8
3
1049600 33792 1280

0
1
3
10