Сіз ұяшықтарды толтыру ойынын ойнап жатырсыз. Ойын интерфейсінде бір қатарға тізілген бірнеше шаршы ұяшық бар, және сіз әр ұяшыққа оң бүтін сан жазуыңыз керек. Содан кейін жүйе сіз толтырған сандар негізінде ұпайды есептейді.

Ойынның әрбір раунды басталмас бұрын жүйе сізге ұяшықтарды толтыруға арналған шектеулерді береді. Ағымдағы ойында бір қатарға тізілген $n$ ұяшық бар делік; жүйе $i$-ші ұяшық үшін екі оң бүтін сан $l_i, r_i$ береді, бұл сіздің $i$-ші ұяшыққа жазатын $x_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$ үзіліссіздігіне сәйкес келеді.