Little Y đang tham quan một công viên. Bản đồ của công viên này có thể được biểu diễn bằng một đồ thị vô hướng đơn liên thông gồm $n$ đỉnh và $m$ cạnh. Để giúp du khách lên kế hoạch lộ trình, trên bản đồ có một số chu trình; mỗi chu trình có thể được biểu diễn bằng một dãy các đỉnh phân biệt $e_1, e_2, \dots, e_l$, trong đó $l \ge 3$, và với mọi $1 \le i \le l$, tồn tại một cạnh trong đồ thị nối $e_i$ và $e_{(i \bmod l)+1}$. Ngoài ra, tập hợp các cạnh nối tất cả các đỉnh theo thứ tự trên chu trình được gọi là tập cạnh của chu trình đó, và hai chu trình được coi là khác nhau khi và chỉ khi tập cạnh của chúng khác nhau. Khi tiếp tục chuyến tham quan, Little Y phát hiện ra một tính chất: mỗi cạnh trong đồ thị xuất hiện trong nhiều nhất một chu trình.

Hiện tại, công viên chưa có hệ thống chiếu sáng, vì vậy khi màn đêm buông xuống, công viên sẽ hoàn toàn chìm trong bóng tối. May mắn thay, các nhân viên đang chuẩn bị đặt các ngọn hải đăng tại một số đỉnh trên bản đồ. Khoảng cách giữa hai đỉnh trên đồ thị được định nghĩa là số cạnh ít nhất phải đi qua để đi từ đỉnh này đến đỉnh kia. Do đó, mỗi ngọn hải đăng, ngoài việc chiếu sáng đỉnh nơi nó được đặt, còn có thể chiếu sáng tất cả các đỉnh có khoảng cách đến đỉnh đó không vượt quá $k$.

Là một thí sinh lập trình thi đấu, Little Y tự nhiên nghĩ ra một câu hỏi: cần đặt ít nhất bao nhiêu ngọn hải đăng để đảm bảo tất cả các đỉnh đều được chiếu sáng?

Dữ liệu vào

Bài toán này gồm nhiều bộ dữ liệu. Dòng đầu tiên chứa một số nguyên $T$ ($1 \le T \le 10^5$), biểu thị số lượng bộ dữ liệu.

Với mỗi bộ dữ liệu:

Dòng đầu tiên chứa ba số nguyên $n, m, k$ ($2 \le n \le 2 \times 10^5$, $n-1 \le m \le 2 \times 10^5$, $1 \le k \le n$), lần lượt biểu thị số đỉnh và số cạnh trên bản đồ, cũng như khoảng cách tối đa mà một ngọn hải đăng có thể chiếu sáng.

$m$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u, v$ ($1 \le u, v \le n, u \ne v$), biểu thị một cạnh trên bản đồ.

Dữ liệu đảm bảo đồ thị vô hướng đã cho là liên thông, không có cạnh bội hay khuyên, và mỗi cạnh xuất hiện trong nhiều nhất một chu trình. Ngoài ra, tổng của $n$ và $m$ trong tất cả các bộ dữ liệu không vượt quá $2 \times 10^5$.

Kết quả

Với mỗi bộ dữ liệu, in ra một số nguyên duy nhất biểu thị số lượng ngọn hải đăng tối thiểu cần đặt.

Ví dụ

Dữ liệu vào

3
5 4 1
1 2
1 3
3 4
1 5
5 5 1
1 2
2 3
3 4
4 5
5 1
8 8 2
1 2
2 3
3 4
4 5
5 1
1 6
2 7
3 8

Kết quả

2
2
1

Ghi chú

Với bộ dữ liệu đầu tiên, có thể đặt hai ngọn hải đăng lần lượt tại đỉnh 1 và đỉnh 4.

Với bộ dữ liệu thứ hai, có thể đặt hai ngọn hải đăng lần lượt tại đỉnh 2 và đỉnh 5.

Với bộ dữ liệu thứ ba, một phương án khả thi là đặt một ngọn hải đăng tại đỉnh 2. Có thể chứng minh rằng đây là phương án duy nhất thỏa mãn điều kiện có số lượng ngọn hải đăng ít nhất.