题目描述

薯条哥有一列正整数组成的数列，支持两种操作：

操作1：选取一个偶数，使其值减半

操作2：选取两个数字，移除并替换为两个数字的和

薯条哥最终希望能够得到一个全为奇数的数列，请计算最少需要操作几次

输入描述

第一行一个数字$T(1\le T\le 10)$，代表测试用例组数

对于每个测试用例：

第一行为$n(1\le n\le 10^5)$，代表数组长度

第二行$n$个正整数，$a_i(1\le a_i\le 10^{14})$

输出描述

对于每个测试用例，输出一个数字，代表最少需要操作次数

样例

输入

3
3
2 4 4
2
1 9
5
1 2 3 4 5

输出

3
0
2