C. Chipmunk Theo and Equality
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

While exploring the depths of the Internet, Theodore the chipmunk found a very interesting sequence of positive integers and decided to play with it.

In one operation, he chooses an element of the sequence and performs the following action:

  • If the chosen element is even, he divides it by 2.
  • If the chosen element is odd, he increases it by 1.

Theo really loves equality, so he wants to make all numbers in the sequence equal (otherwise, some numbers might feel offended). Since he needs to plan his lunch time, help him determine the minimum number of operations required to make all numbers equal.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — the length of the sequence.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the elements of the sequence.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.

Output

For each test case, output a single integer — the minimum number of operations Theo needs to make all numbers in the sequence equal.

Example
Input
5
3
3 2 4
7
3 6 7 16 8 8 7
3
1 4 2
5
10 10 10 10 10
6
1 1 3 1 1 1
Output
3
11
2
0
3
Note

In the first test case, we have a sequence: $$$[3, 2, 4]$$$

One possible sequence of operations: $$$$$$ [\textbf{3}, 2, 4] \rightarrow [\textbf{4}, 2, 4] \rightarrow [2, 2, \textbf{4}] \rightarrow [2, 2, 2] $$$$$$ (Operations are performed on numbers shown in bold.)

In the second test case, the sequence is: $$$[3, 6, 7, 16, 8, 8, 7]$$$

Possible operations:

  • Perform the operation once on the 1st element: $$$3 \rightarrow 4$$$
  • Perform the operation twice on the 2nd element: $$$6 \rightarrow 3 \rightarrow 4$$$
  • Perform the operation twice on the 4th element: $$$7 \rightarrow 8 \rightarrow 4$$$
  • Perform the operation twice on the 5th element: $$$16 \rightarrow 8 \rightarrow 4$$$
  • Perform the operation once on the 6th element: $$$8 \rightarrow 4$$$
  • Perform the operation once on the 7th element: $$$8 \rightarrow 4$$$
  • Perform the operation twice on the 8th element: $$$7 \rightarrow 8 \rightarrow 4$$$

After these $$$11$$$ operations, all elements become $$$4$$$.