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

Даны два массива $$$a$$$ и $$$b$$$ длины $$$n$$$.

Вы можете любое количество раз (возможно, ноль) выполнить следующую операцию: выбрать индекс $$$i$$$ ($$$1 \leq i \leq n$$$) и поменять местами $$$a_i$$$ и $$$b_i$$$.

Назовем стоимостью массива $$$a$$$ величину, равную $$$\sum_{i=1}^{n} \sum_{j=i + 1}^{n} (a_i + a_j)^2$$$. Аналогично, стоимость массива $$$b$$$ будет равна $$$\sum_{i=1}^{n} \sum_{j=i + 1}^{n} (b_i + b_j)^2$$$.

Вам необходимо минимизировать суммарную стоимость двух массивов.

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

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

В первой строке каждого набора входных данных содержится целое число $$$n$$$ ($$$1 \leq n \leq 100$$$) — длина обоих массивов.

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

В третей строке каждого набора входных данных содержатся $$$n$$$ целых чисел $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \leq b_i \leq 100$$$) — элементы второго массива.

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

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

Для каждого набора входных данных выведите минимальную возможную суммарную стоимость двух массивов.

Пример
Входные данные
3
1
3
6
4
3 6 6 6
2 7 4 1
4
6 7 2 4
2 5 3 5
Выходные данные
0
987
914
Примечание

Во втором наборе входных данных в одном из оптимальных ответов после выполнения операций $$$a = [2, 6, 4, 6]$$$, $$$b = [3, 7, 6, 1]$$$.

Стоимость массива $$$a$$$ равна $$$(2 + 6)^2 + (2 + 4)^2 + (2 + 6)^2 + (6 + 4)^2 + (6 + 6)^2 + (4 + 6)^2 = 508$$$.

Стоимость массива $$$b$$$ равна $$$(3 + 7)^2 + (3 + 6)^2 + (3 + 1)^2 + (7 + 6)^2 + (7 + 1)^2 + (6 + 1)^2 = 479$$$.

Суммарная стоимость массивов равна $$$508 + 479 = 987$$$.