İki anbarın birləşdirilməsi

Johnun fermasını sahələr şəbəkəsinə çevirdikdə, n sayda sahə var və bunlar ardıcıl olaraq 1..n nömrələnib. Bu sahələr arasında m (0 ≤ m ≤ 10^5) cüt sahəni birləşdirən ikitərəfli yollar mövcuddur.

Bu fermada iki anbar var - biri sahə 1-də, digəri isə sahə n-də yerləşir. JD, anbarlar arasında yollar ardıcıllığı ilə bir yolun olmasını təmin etmək istəyir. Bu məqsədlə, iki yeni yol inşa etməyə hazırdırlar. Sahələr i və j arasında bir yol inşa etməyin dəyəri (i − j) ^ 2-dir.

JD-yə anbarlar 1 və n arasında keçid təmin etmək üçün minimal xərci müəyyənləşdirməkdə kömək edin.

Giriş Məlumatları

Birinci sətir t (1 ≤ t ≤ 20) testlərin sayını ehtiva edir.

Hər bir test iki tam ədəd n (1 ≤ n ≤ 10^5) və m ilə başlayır. Sonrakı m sətirin hər biri iki tam ədəd i və j ehtiva edir, bu da iki fərqli sahə i və j arasında bir yol olduğunu göstərir. Hər hansı iki sahə arasında ən çox bir yolun olduğu və bütün alt testlər üçün n + m cəminin 5 * 10^5-dən çox olmadığı təmin edilir.

Çıxış Məlumatları

t sətir çıxarın. i-ci sətir i-ci test üçün minimal xərci ehtiva edən bir tam ədəd olmalıdır.

Nümunə

Birinci testdə optimal olaraq sahələri 2 və 3, həmçinin sahələri 3 və 4 birləşdirməkdir.

İkinci testdə optimal olaraq sahələri 3 və 4 birləşdirməkdir. İkinci yol tələb olunmur.