Quốc đảo Byteland có ~N~ hòn đảo được đánh số từ 1 đến ~N~, các hòn đảo được nối với nhau bằng ~M~ cây cầu, mỗi cây cầu nối 2 hòn đảo khác nhau đảm bảo đi lại bằng đường bộ giữa 2 hòn đảo được nối. Có hai trung tâm kinh tế lần lượt nằm ở đảo 1 và đảo ~N~. Quốc vương muốn đảm bảo đi lại giữa 2 trung tâm kinh tế này bằng đường bộ bằng cách xây dựng thêm không quá 2 cây cầu mới. Chi phí xây dựng một cây cầu nối đảo ~i~ và đảo ~j~ là ~(i - j)^2~.

Xác định tổng chi phí nhỏ nhất cần dùng để xây cầu đảm bảo yêu cầu của quốc vương.

Input

• Dòng đầu gồm một nguyên dương ~T~ (~1 \le T \le 20~) là số lượng bộ test. Các dòng tiếp theo ghi thông tin của ~T~ bộ test, thông tin mỗi test gồm:
• Dòng đầu ghi 2 số nguyên dương ~N, M~ (~1 \le N \le 10^5, 0 \le M \le 10^5~);
• Trong ~M~ dòng tiếp theo, mỗi dòng ghi 2 số nguyên ~u, v~ là số hiệu 2 hòn đảo đã được nối bởi một cây cầu. Tổng số ~N + M~ trong tất cả các test không quá ~5 \times 10^5~.

Output

• Gồm ~T~ dòng, mỗi dòng ghi kết quả tương ứng của một test.