Ви граєте в гру із заповненням клітинок. На ігровому інтерфейсі в ряд розташовано декілька клітинок, і вам потрібно вписати в кожну клітинку додатне ціле число. Потім система обчислить бали на основі чисел, які ви вписали.

Перед початком кожного раунду гри система надає обмеження для заповнення клітинок. Нехай у поточній грі в ряд розташовано $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$.