Bạn đang chơi một trò chơi điền số vào lưới. Trên giao diện trò chơi, một số ô vuông được xếp thành một hàng ngang và bạn cần điền vào mỗi ô một số nguyên dương. Sau đó, hệ thống sẽ tính điểm dựa trên các con số mà bạn đã điền.

Trước khi mỗi ván chơi bắt đầu, hệ thống sẽ cung cấp cho bạn các ràng buộc khi điền ô. Giả sử có $n$ ô vuông xếp thành một hàng trong ván hiện tại, hệ thống sẽ cung cấp hai số nguyên dương $l_i, r_i$ cho ô thứ $i$, cho biết số $x_i$ mà bạn điền vào ô thứ $i$ phải thỏa mãn $l_i \le x_i \le r_i$. Sau khi bạn điền xong các số, hệ thống sẽ chia dãy ô vuông thành một số đoạn liên tiếp dựa trên các ô kề nhau có số khác nhau. Tiếp theo, hệ thống sẽ tính tổng bình phương độ dài của mỗi đoạn, giá trị này được gọi là độ liên tục của phương án điền số.

Ví dụ, với phương án điền số $x = [1, 1, 3, 3, 5, 5, 5, 3, 3]$, kết quả chia đoạn là $\underline{1, 1}, \underline{3, 3}, \underline{5, 5, 5}, \underline{3, 3}$, và độ liên tục tương ứng là $2^2 + 2^2 + 3^2 + 2^2 = 21$.

Mục tiêu của trò chơi này là cực tiểu hóa độ liên tục. Bạn cần xác định giá trị nhỏ nhất của độ liên tục theo chiến lược điền số tối ưu.

Dữ liệu vào

Bạn cần trả lời cho nhiều ván chơi. Dòng đầu tiên chứa một số nguyên $T$ ($1 \le T \le 10^5$), biểu thị số ván chơi.

Đối với mỗi ván chơi:

Dòng đầu tiên của dữ liệu vào chứa một số nguyên dương $n$ ($1 \le n \le 10^6$), biểu thị số lượng ô vuông.

Dòng tiếp theo chứa $n$ số nguyên dương $l_i$ ($1 \le l_i \le 10^9$), biểu thị ràng buộc cận dưới cho mỗi ô vuông.

Dòng tiếp theo nữa chứa $n$ số nguyên dương $r_i$ ($1 \le r_i \le 10^9, l_i \le r_i$), biểu thị ràng buộc cận trên cho mỗi ô vuông.

Dữ liệu đảm bảo tổng của $n$ qua tất cả các ván chơi không vượt quá $10^6$.

Dữ liệu ra

Đối với mỗi ván chơi, in ra một số nguyên duy nhất biểu thị giá trị nhỏ nhất của độ liên tục.

Ví dụ

Dữ liệu vào mẫu 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

Dữ liệu ra mẫu 1

3
6
17

Ghi chú

Ở ván chơi thứ nhất, một phương án điền số khả dĩ là $x = [3, 1, 4]$, tương ứng với độ liên tục là $1^2 + 1^2 + 1^2 = 3$.

Ở ván chơi thứ hai, một phương án điền số khả dĩ là $x = [1, 2, 3, 4, 5, 6]$, tương ứng với độ liên tục là $1^2 + 1^2 + 1^2 + 1^2 + 1^2 + 1^2 = 6$.

Ở ván chơi thứ ba, một phương án điền số khả dĩ là $x = [1, 1, 2, 2, 2, 1, 1]$, tương ứng với độ liên tục là $2^2 + 3^2 + 2^2 = 17$.