34913번 - Collatz Conjecture 다국어

문제

Busy Beaver recently learned about the Collatz Conjecture! He has written down a sequence of $N$ positive integers $a_1, a_2, \ldots , a_N$ on a blackboard to experiment with and further his understanding of the conjecture. He also notices a counter left on a table and comes up with the following game to play.

The counter initially starts at the number 1ドル$. A move consists of picking a number on the blackboard and replacing it:

• If the counter shows an odd number, Busy Beaver must pick some odd number $x$ on the board and replace it with 3ドルx+1$.
• If the counter shows an even number, he must pick some even number $y$ on the board and replace it with $\frac{y}{2}$.

After each replacement, Busy Beaver increments the counter by 1ドル$. If he cannot make any move, the game ends, and his score is the number of moves he performed (equivalently, one less than the number on the counter).

Busy Beaver wants to play this game for as long as possible. Help him determine the maximum number of moves he can perform before he runs out of moves!

입력

The first line contains the number of test cases $T$ (1ドル \le T \le 500$).

The first line of each test case contains a single integer $N$ (1ドル \le N \le 500$), the number of positive integers on the blackboard.

The second line of each test case contains $N$ positive integers $a_1, a_2, \ldots , a_N$ (1ドル \le a_i \le 10^6$). It can be shown that any Collatz sequence started on a number at most 10ドル^6$ will reach 1ドル$ after at most 524ドル$ moves. Additionally, it can also be shown that Busy Beaver will eventually run out of moves and that he never writes a number larger than 10ドル^{18}$ on the blackboard.

The sum of $N$ across all test cases does not exceed 500ドル$.

출력

For each test case, output a single integer --- the maximum number of moves that Busy Beaver can perform.

제한

노트

In the first test case, Busy Beaver only has one number on the blackboard which is the number 3ドル$.

• On the first move, Busy Beaver replaces the odd number 3ドル$ with 3ドル(3) + 1 = 10$.
• On the second move, Busy Beaver replaces the even number 10ドル$ with $\frac{10}{2} = 5$.
• On the third move, Busy Beaver replaces the odd number 5ドル$ with 3ドル(5) + 1 = 16$.
• On the fourth move, Busy Beaver replaces the even number 16ドル$ with $\frac{16}{2} = 8$.

At this point, Busy Beaver cannot make any moves, so the maximum number of moves is 4ドル$.

In the second test case, Busy Beaver cannot make any move since there are no odd numbers on the blackboard.