C. Мастер последовательностей
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Для некоторого положительного целого числа $$$m$$$ YunQian считает массив $$$q$$$ из $$$2m$$$ (возможно, отрицательных) целых чисел хорошим, если и только если для каждой подпоследовательности $$$q$$$, имеющей длину $$$m$$$, произведение $$$m$$$ элементов в подпоследовательности равно сумме оставшихся $$$m$$$ элементов. Формально, пусть $$$U=\{1,2,\ldots,2m\}$$$. Для всех множеств $$$S \subseteq U$$$ таких, что $$$|S|=m$$$, должно выполняться $$$\prod\limits_{i \in S} q_i = \sum\limits_{i \in U \setminus S} q_i$$$.

Определим расстояние между двумя массивами $$$a$$$ и $$$b$$$ длиной $$$k$$$ как $$$\sum\limits_{i=1}^k|a_i-b_i|$$$.

Вам дано целое положительное число $$$n$$$ и массив $$$p$$$ из $$$2n$$$ целых чисел.

Найдите минимальное расстояние между $$$p$$$ и $$$q$$$ среди всех хороших массивов $$$q$$$ длины $$$2n$$$. Можно показать, что для всех положительных целых чисел $$$n$$$ существует хотя бы один хороший массив. Обратите внимание, что вам не требуется предъявлять массив $$$q$$$, который достигает этого минимального расстояния.

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

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

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1\le n\le 2\cdot10^5$$$).

Вторая строка каждого набора содержит $$$2n$$$ целых чисел $$$p_1, p_2, \ldots, p_{2n}$$$ ($$$|p_i| \le 10^9$$$).

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

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

Для каждого набора выведите минимальное расстояние между $$$p$$$ и $$$q$$$.

Пример
Входные данные
4
1
6 9
2
1 2 2 1
2
-2 -2 2 2
4
-3 -2 -1 0 1 2 3 4
Выходные данные
3
2
5
13
Примечание

В первом наборе оптимальный массив $$$q=[6,6]$$$.

Во втором наборе оптимальный массив $$$q=[2,2,2,2]$$$.