Busy Beaver 最近了解了考拉兹猜想（Collatz Conjecture）！他在黑板上写下了一个由 $N$ 个正整数组成的序列 $a_1, a_2, \dots, a_N$，以此来进行实验并加深对该猜想的理解。 他还注意到桌上放着一个计数器，并想出了以下游戏来玩。

计数器最初从数字 $1$ 开始。一次操作包括选择黑板上的一个数并将其替换：

• 如果计数器显示的是一个奇数，Busy Beaver 必须选择黑板上的某个奇数 $x$，并将其替换为 $3x + 1$。
• 如果计数器显示的是一个偶数，他必须选择黑板上的某个偶数 $y$，并将其替换为 $\frac{y}{2}$。

每次替换后，Busy Beaver 会将计数器加 $1$。如果他无法进行任何操作，游戏结束，他的得分是他进行的操作次数（等价于计数器上的数字减 $1$）。

Busy Beaver 想要尽可能久地玩这个游戏。请帮助他确定在无路可走之前，他最多可以进行多少次操作！

输入格式

第一行包含测试用例的数量 $T$ ($1 \le T \le 500$)。

每个测试用例的第一行包含一个整数 $N$ ($1 \le N \le 500$)，表示黑板上正整数的个数。

每个测试用例的第二行包含 $N$ 个正整数 $a_1, a_2, \dots, a_N$ ($1 \le a_i \le 10^6$)。可以证明，任何从不超过 $10^6$ 的数开始的考拉兹序列，在最多 $524$ 次操作后都会到达 $1$。此外，还可以证明 Busy Beaver 最终一定会无路可走，且他永远不会在黑板上写下大于 $10^{18}$ 的数。

所有测试用例中 $N$ 的总和不超过 $500$。

输出格式

对于每个测试用例，输出一个整数——Busy Beaver 最多可以进行的操作次数。

样例

输入样例 1

6
1
3
5
2 4 6 8 10
6
4 5 6 6 5 4
26
837799 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
9
3 1 4 1 5 9 2 6 5
10
123456 678910 111213 141516 171819 202122 232425 262728 293031 323334

输出样例 1

4
0
14
164
34
60

说明

在第一个测试用例中，Busy Beaver 的黑板上只有一个数字，即数字 $3$。

• 在第一次操作中，Busy Beaver 将奇数 $3$ 替换为 $3(3) + 1 = 10$。
• 在第二次操作中，Busy Beaver 将偶数 $10$ 替换为 $\frac{10}{2} = 5$。
• 在第三次操作中，Busy Beaver 将奇数 $5$ 替换为 $3(5) + 1 = 16$。
• 在第四次操作中，Busy Beaver 将偶数 $16$ 替换为 $\frac{16}{2} = 8$。

此时，Busy Beaver 无法进行任何操作，因此最大操作次数为 $4$。

在第二个测试用例中，Busy Beaver 无法进行任何操作，因为黑板上没有奇数。