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

Монокарп планирует провести соревнование по смешанным единоборствам. В нем будет три весовых категории: легкий вес, средний вес и тяжелый вес. Победитель в каждой категории определяется по системе плей-офф.

В частности, это подразумевает, что количество участников в каждой категории должно быть степенью двойки. Дополнительно в каждой категории должно быть ненулевое количество участников.

$$$n$$$ участников уже зарегистрировались на соревнование, $$$i$$$-й из них весит $$$a_i$$$. Чтобы разделить участников на категории, Монокарп планирует установить две целых границы весов $$$x$$$ и $$$y$$$ ($$$x < y$$$).

Все участники с весом строго меньше $$$x$$$ будут считаться легким весов. Все участники с весом больше или равно $$$y$$$, будут считаться тяжелым весом. Все остальные участники будут считаться средним весом.

Возможно, что распределение не сделает количество участников в каждой категории степенью двойки. Оно так же может сделать и пустые категории. Чтобы решить эти проблемы, Монокарп может пригласить любое количество участников в каждую категории.

Обратите внимание, что Монокарп не может выгнать никого из $$$n$$$ участников, которые уже зарегистрировались на соревнование.

Однако, он хочет пригласить как можно меньше дополнительных участников. Помогите Монокарпу выбрать $$$x$$$ и $$$y$$$ таким образом, чтобы суммарное количество необходимых дополнительных участников было как можно меньше. Выведите это количество.

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

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

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

Во второй строке каждого набора входных данных записаны $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$) — веса зарегистрированных участников.

Сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

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

На каждый набор входных данных выведите одно целое число — наименьшее количество дополнительных участников, которых Монокарпу необходимо пригласить после того, как он выберет границы весов $$$x$$$ и $$$y$$$.

Пример
Входные данные
4
4
3 1 2 1
1
1
6
2 2 2 1 1 1
8
6 3 6 3 6 3 6 6
Выходные данные
0
2
3
2
Примечание

В первом наборе входных данных Монокарп может выбрать $$$x=2$$$ и $$$y=3$$$. Легкая, средняя и тяжелая весовые категории будут содержать $$$2$$$, $$$1$$$ и $$$1$$$ участников, соответственно. Они все являются степенями двойки, поэтому дополнительных участников не нужно.

Во втором наборе входных данных вне зависимости от выбора $$$x$$$ и $$$y$$$ в одной категории будет $$$1$$$ участник, в остальных — $$$0$$$. Монокарпу придется пригласить $$$1$$$ участника в обе из оставшихся категорий.

В третьем наборе входных данных Монокарп может выбрать $$$x=1$$$ и $$$y=2$$$. Легкая, средняя и тяжелая весовые категории будут содержать $$$0$$$, $$$3$$$ и $$$3$$$ участников, соответственно. В каждую категорию придется пригласить по одному участнику.

В четвертом наборе входных данных Монокарп может выбрать $$$x=8$$$ и $$$y=9$$$. Легкая, средняя и тяжелая весовые категории будут содержать $$$8$$$, $$$0$$$ и $$$0$$$ участников, соответственно. В среднюю и тяжелую категории придется пригласить по одному участнику.