C. Бурундучонок Тео и равенство
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Бурундучонок Тео, исследуя глубины интернета, нашёл очень интересную для себя последовательность целых положительных чисел и решил с ней поиграть. Он уже решил для себя, что за одну операцию он будет выбирать элемент последовательности и проделывать с ним следующее действие:

  • Если выбранный элемент чётный, то он делит его на 2.
  • Если выбранный элемент нечётный, то он увеличивает его на 1.

Тео очень любит равенство, и поэтому хочет сделать все числа последовательности одинаковыми (иначе некоторым числам может быть обидно). Так как ему нужно планировать своё время обеда, то помогите узнать, какое минимальное количество операций ему потребуется, чтобы сделать все числа равными.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

В первой строке каждого набора входных данных содержится единственное число $$$n$$$ ($$$1 \le n \le 10^5$$$) — длина последовательности.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — элементы последовательности.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$10^5$$$.

Выходные данные

Для каждого набора входных данных выведите единственное число — минимальное количество операций, которое нужно совершить Тео, чтобы сделать все числа последовательности одинаковыми.

Пример
Входные данные
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
Выходные данные
3
11
2
0
3
Примечание

В первом наборе входных данных у нас есть последовательность: $$$[3, 2, 4]$$$

Один из возможных наборов операций: $$$$$$ [\textbf{3}, 2, 4] \rightarrow [\textbf{4}, 2, 4] \rightarrow [2, 2, \textbf{4}] \rightarrow [2, 2, 2] $$$$$$ (Операции выполняются над числами, выделенными жирным шрифтом.)

Во втором наборе входных данных последовательность такова: $$$[3, 6, 7, 16, 8, 8, 7]$$$

Возможные операции:

  • Выполнить операцию один раз над 1-м элементом: $$$3 \rightarrow 4$$$
  • Выполнить операцию два раза над 2-м элементом: $$$6 \rightarrow 3 \rightarrow 4$$$
  • Выполнить операцию два раза над 4-м элементом: $$$7 \rightarrow 8 \rightarrow 4$$$
  • Выполнить операцию два раза над 5-м элементом: $$$16 \rightarrow 8 \rightarrow 4$$$
  • Выполнить операцию один раз над 6-м элементом: $$$8 \rightarrow 4$$$
  • Выполнить операцию один раз над 7-м элементом: $$$8 \rightarrow 4$$$
  • Выполнить операцию два раза над 8-м элементом: $$$7 \rightarrow 8 \rightarrow 4$$$

После этих $$$11$$$ операций все элементы становятся равны $$$4$$$.