Вы играете в игру с заполнением клеток. На игровом экране в ряд расположено несколько клеток, и вам нужно вписать в каждую клетку положительное целое число. Затем система подсчитает очки на основе вписанных вами чисел.

Перед началом каждого раунда игры система предоставляет ограничения на заполнение клеток. Пусть в текущей игре в ряд расположены $n$ клеток; тогда для $i$-й клетки система задаёт два положительных целых числа $l_i, r_i$, означающих, что число $x_i$, которое вы впишете в $i$-ю клетку, должно удовлетворять условию $l_i \le x_i \le r_i$. После того как вы заполните все клетки, система разобьёт последовательность клеток на несколько отрезков по границам между соседними клетками с различными числами. Затем система вычислит сумму квадратов длин всех отрезков, которая называется непрерывностью схемы заполнения.

Например, для схемы заполнения $x = [1, 1, 3, 3, 5, 5, 5, 3, 3]$ результатом разбиения на отрезки будет $\underline{1, 1}, \underline{3, 3}, \underline{5, 5, 5}, \underline{3, 3}$, а непрерывность равна $2^2 + 2^2 + 3^2 + 2^2 = 21$.

Цель этой игры — минимизировать непрерывность. Вам необходимо определить минимальное значение непрерывности при оптимальной стратегии заполнения.

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

Вам нужно ответить для нескольких раундов игры. Первая строка содержит целое число $T$ ($1 \le T \le 10^5$), обозначающее количество раундов игры.

Для каждого раунда игры:

Первая строка входных данных содержит положительное целое число $n$ ($1 \le n \le 10^6$), обозначающее количество клеток.

Следующая строка содержит $n$ положительных целых чисел $l_i$ ($1 \le l_i \le 10^9$), обозначающих нижние границы для каждой клетки.

Следующая за ней строка содержит $n$ положительных целых чисел $r_i$ ($1 \le r_i \le 10^9, l_i \le r_i$), обозначающих верхние границы для каждой клетки.

Гарантируется, что общая сумма $n$ по всем играм не превышает $10^6$.

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

Для каждого раунда игры выведите одно целое число — минимальное значение непрерывности.

Пример

Пример входных данных 1

3
3
1 1 4
5 1 4
6
1 2 3 4 4 4
3 3 3 4 5 6
7
1 1 2 2 1 1 1
1 2 2 2 2 1 1

Пример выходных данных 1

3
6
17

Примечание

В первом раунде игры одной из возможных схем заполнения является $x = [3, 1, 4]$, что соответствует непрерывности $1^2 + 1^2 + 1^2 = 3$.

Во втором раунде игры одной из возможных схем заполнения является $x = [1, 2, 3, 4, 5, 6]$, что соответствует непрерывности $1^2 + 1^2 + 1^2 + 1^2 + 1^2 + 1^2 = 6$.

В третьем раунде игры одной из возможных схем заполнения является $x = [1, 1, 2, 2, 2, 1, 1]$, что соответствует непрерывности $2^2 + 3^2 + 2^2 = 17$.