Harmonious Lineup

Một vị nhạc trưởng đang chuẩn bị cho một buổi hòa nhạc lớn và sắp xếp các nghệ sĩ tham gia.

Nhạc trưởng có $n$ nghệ sĩ được đánh số từ $1$ đến $n$. Họ được xếp thành một hàng theo thứ tự: $1, 2, 3, ..., n$.

Nhạc trưởng có một danh sách gồm $m$ cặp nghệ sĩ có mâu thuẫn với nhau. Bất kỳ cặp nghệ sĩ nào không xuất hiện trong danh sách này đều hòa hợp với nhau.

Một đoạn liên tiếp trong hàng bắt đầu từ nghệ sĩ $a$ và kết thúc tại nghệ sĩ $b$ là $[a, a + 1, a + 2, ..., b]$. Một đoạn được gọi là hòa hợp nếu mọi cặp nghệ sĩ trong đoạn đó đều hòa hợp với nhau.

Nhạc trưởng muốn biết có bao nhiêu cặp $(a, b)$ thỏa mãn $1 ≤ a ≤ b ≤ n$ sao cho đoạn bắt đầu từ nghệ sĩ $a$ và kết thúc tại nghệ sĩ $b$ là một đoạn hòa hợp.

Dữ liệu vào

Dữ liệu vào gồm nhiều bộ test. Dòng đầu tiên chứa một số nguyên $t$ ($1 ≤ t ≤ 2 · 10^4$) là số lượng bộ test. Phần mô tả của các bộ test tiếp nối sau đó.

Dòng đầu tiên của mỗi bộ test chứa hai số nguyên $n$ ($2 ≤ n ≤ 10^5$) và $m$ ($0 ≤ m ≤ 10^5$) lần lượt là số lượng nghệ sĩ và số lượng cặp nghệ sĩ có mâu thuẫn.

Dòng thứ $i$ trong số $m$ dòng tiếp theo chứa hai số nguyên $x_i$ và $y_i$ ($1 ≤ x_i, y_i ≤ n$, $x_i ≠ y_i$) biểu diễn một cặp nghệ sĩ có mâu thuẫn với nhau. Các cặp này có thể bị lặp lại.

Dữ liệu đảm bảo rằng tổng của $n$ trên tất cả các bộ test không vượt quá $10^5$ ($\sum n ≤ 10^5$), và tổng của $m$ trên tất cả các bộ test không vượt quá $10^5$ ($\sum m ≤ 10^5$).

Kết quả

Với mỗi bộ test, in ra một số nguyên là số lượng đoạn hòa hợp.

Chấm điểm

Subtask 1 (15 points). $m = 0$

Subtask 2 (25 points). $\sum n ≤ 2000$; $\sum m ≤ 2000$

Subtask 3 (60 points). $1 ≤ t ≤ 2 · 10^4$; $2 ≤ n ≤ 10^5$; $0 ≤ m ≤ 10^5$; $\sum n ≤ 10^5$; $\sum m ≤ 10^5$

Ví dụ

Input

1
4 1
1 4

Output

9

Ghi chú

Trong ví dụ, kết quả là $9$. Tổng cộng có $10$ đoạn con, chỉ có đoạn $[1, 2, 3, 4]$ chứa cả hai nghệ sĩ có mâu thuẫn là $1$ và $4$, do đó có $9$ đoạn hòa hợp là: $[1]$, $[2]$, $[3]$, $[4]$, $[1, 2]$, $[2, 3]$, $[3, 4]$, $[1, 2, 3]$ và $[2, 3, 4]$.