Монокарп планирует провести соревнование по смешанным единоборствам. В нем будет три весовых категории: легкий вес, средний вес и тяжелый вес. Победитель в каждой категории определяется по системе плей-офф.
В частности, это подразумевает, что количество участников в каждой категории должно быть степенью двойки. Дополнительно в каждой категории должно быть ненулевое количество участников.
$$$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$$$.
443 1 2 11162 2 2 1 1 186 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$$$ участников, соответственно. В среднюю и тяжелую категории придется пригласить по одному участнику.
