Cho một đồ thị ~N~ đỉnh, đánh số từ ~0~ đến ~N~ - ~1~. Ban đầu đồ thị không có cạnh nào. Lần lượt thêm vào đồ thị ~M~ cạnh vô hướng (~u~, ~v~) với (~0 \le u~, ~v \le N~ - ~1~). Sau mỗi lần thêm ~1~ cạnh, in ra số lượng cầu hiện có trong đồ thị. Dữ liệu đảm bảo không có yêu cầu thêm vào ~1~ cạnh đã tồn tại, hoặc ~1~ cạnh nối ~1~ đỉnh với chính nó.

Input

Dòng đầu ghi số nguyên ~T~ (~T \le 10~) là số lượng bộ test. Mỗi bộ test bắt đầu bằng ~2~ số nguyên ~N~ (~1 \le N \le 50000~) và ~M~ (~1 \le M \le 100000~), theo sau là ~M~ dòng, mỗi dòng ghi ~1~ cặp số nguyên (~u~, ~v~) thể hiện một yêu cầu thêm vào cạnh (~u~, ~v~).

Output

Sau mỗi yêu cầu thêm cạnh, in ra 1 số nguyên trên 1 dòng là số lượng cầu hiện có trong đồ thị.

Sample Input

1
5 10
3 0
0 2
1 0
1 3
1 4
2 4
4 0
2 1
2 3
3 4

Sample Output

1
2
3
1
2
0
0
0
0
0