J. How Kifah sees Extreme?
time limit per test
1.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

In a parallel universe, a contest has been organized by advanced problem setters, and $$$\textit{Kifah}$$$ is one of them. The chief judge asked $$$\textit{Kifah}$$$ to set an extreme problem. Unfortunately, $$$\textit{Kifah}$$$ didn't understand the meaning of "extreme problem" and was too shy to ask for clarification. It's possible that he understood "extreme" in the opposite sense. As the problem is being held in a far universe, no one can catch $$$\textit{Kifah}$$$, and the contestants cannot seek revenge.

Unfortunately for you, there is a bug in the universe's system which directed the problem to your contest. I'm sorry for that, and I hope you enjoy your hard luck.

In this Problem you will be given an array $$$a_1,a_2,...,a_n$$$.

You can do the following operation any number of times. During each operation you can choose one element $$$a_i$$$ from the array and do one of the following two actions:

  • Choose one bit from the binary representation of $$$a_i$$$ and turn it off.
  • Choose two bits from the binary representation of $$$a_i$$$ and turn them both on (the two chosen bits have to be both zeros before turning them on)

What is the minimum number of operations you have to do to make all elements of array $$$a$$$ equal.

Input

The first line contains a single integer $$$t$$$ $$$(1 \le t \le 10)$$$ — the number of test cases.

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

The second line contains $$$n$$$ integers $$$a_1,a_2,\dots,a_n$$$ $$$(0 \le a_i \le 10^5)$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$10^5$$$.

Output

For each test case, print one integer — the minimum number of operations you have to do to make all elements of the array equal.

Example
Input
1
4
1 2 3 2
Output
4
Note

In the example, the solution could be done in the following order:

$$$[1 , 2 , 3 , 2]$$$ $$$\rightarrow$$$ $$$[7 , 2 , 3 , 2]$$$ $$$\rightarrow$$$ $$$[6 , 2 , 3 , 2]$$$ $$$\rightarrow$$$ $$$[6 , 2 , 2, 2 ]$$$ $$$\rightarrow$$$ $$$[2 , 2 , 2 , 2]$$$