Anda sedang memainkan permainan mengisi petak. Pada antarmuka permainan, beberapa petak persegi disusun dalam satu baris, dan Anda perlu mengisi setiap petak dengan sebuah bilangan bulat positif. Sistem kemudian akan menghitung skor berdasarkan bilangan-bilangan yang Anda isikan.

Sebelum setiap ronde permainan dimulai, sistem akan memberikan batasan untuk mengisi petak-petak tersebut. Misalkan terdapat $n$ petak yang disusun dalam satu baris untuk permainan saat ini, sistem akan memberikan dua bilangan bulat positif $l_i, r_i$ untuk petak ke-$i$, yang menyatakan bahwa bilangan $x_i$ yang Anda isikan pada petak ke-$i$ harus memenuhi $l_i \le x_i \le r_i$. Setelah Anda mengisi semua bilangan, sistem akan memisahkan barisan petak menjadi beberapa segmen berdasarkan petak-petak bersebelahan yang memiliki bilangan berbeda. Sistem kemudian akan menghitung jumlah kuadrat dari panjang setiap segmen, yang disebut sebagai kontinuitas dari skema pengisian tersebut.

Sebagai contoh, untuk skema pengisian $x = [1, 1, 3, 3, 5, 5, 5, 3, 3]$, hasil segmentasinya adalah $\underline{1, 1}, \underline{3, 3}, \underline{5, 5, 5}, \underline{3, 3}$, dan kontinuitasnya bersesuaian dengan $2^2 + 2^2 + 3^2 + 2^2 = 21$.

Tujuan dari permainan ini adalah meminimalkan kontinuitas. Anda perlu menentukan nilai minimum dari kontinuitas di bawah strategi pengisian yang optimal.

Masukan

Anda perlu menjawab untuk beberapa ronde permainan. Baris pertama berisi sebuah bilangan bulat $T$ ($1 \le T \le 10^5$), yang menyatakan banyaknya ronde permainan.

Untuk setiap ronde permainan:

Baris pertama masukan berisi sebuah bilangan bulat positif $n$ ($1 \le n \le 10^6$), yang menyatakan banyaknya petak.

Baris berikutnya berisi $n$ bilangan bulat positif $l_i$ ($1 \le l_i \le 10^9$), yang menyatakan batasan batas bawah untuk setiap petak.

Baris selanjutnya berisi $n$ bilangan bulat positif $r_i$ ($1 \le r_i \le 10^9, l_i \le r_i$), yang menyatakan batasan batas atas untuk setiap petak.

Dijamin bahwa jumlah total $n$ di seluruh permainan tidak melebihi $10^6$.

Keluaran

Untuk setiap ronde permainan, keluarkan sebuah bilangan bulat tunggal yang menyatakan nilai minimum dari kontinuitas.

Contoh

Contoh Masukan 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

Contoh Keluaran 1

3
6
17

Catatan

Untuk ronde pertama permainan, salah satu skema pengisian yang mungkin adalah $x = [3, 1, 4]$, yang bersesuaian dengan kontinuitas sebesar $1^2 + 1^2 + 1^2 = 3$.

Untuk ronde kedua permainan, salah satu skema pengisian yang mungkin adalah $x = [1, 2, 3, 4, 5, 6]$, yang bersesuaian dengan kontinuitas sebesar $1^2 + 1^2 + 1^2 + 1^2 + 1^2 + 1^2 = 6$.

Untuk ronde ketiga permainan, salah satu skema pengisian yang mungkin adalah $x = [1, 1, 2, 2, 2, 1, 1]$, yang bersesuaian dengan kontinuitas sebesar $2^2 + 3^2 + 2^2 = 17$.