Bãi mìn kỳ lạ

Trên mặt phẳng toạ độ có $n$ quả mìn. Quả mìn thứ $i$ nằm tại ô $(x_i,y_i)$ và có bộ đếm $t_i$: sau đúng $t_i$ giây kể từ lúc bắt đầu, nó tự phát nổ.

Khi một quả mìn tại $(x,y)$ nổ, nó lập tức kích nổ mọi quả mìn cùng hàng hoặc cùng cột với nó ở khoảng cách không quá $k$, tức là mọi quả mìn tại $(x,y^{\prime })$ với $|y-y^{\prime }|\le k$ và mọi quả mìn tại $(x^{\prime },y)$ với $|x-x^{\prime }|\le k$ (vùng nổ có hình dấu cộng). Các quả mìn vừa bị kích nổ lại tiếp tục kích nổ những quả khác theo đúng quy tắc trên, tạo thành phản ứng dây chuyền. Mọi vụ nổ và phản ứng dây chuyền đều xảy ra tức thời.

Ngoài ra, tại mỗi giây $0,1,2,\dots$ bạn được chọn đúng một quả mìn chưa nổ và kích nổ nó bằng tay (phản ứng dây chuyền cũng xảy ra như trên).

Hãy tìm số giây nhỏ nhất để tất cả các quả mìn đều đã nổ.

Dữ liệu vào

• Dòng đầu chứa số nguyên $q$ là số bộ dữ liệu.
• Mỗi bộ dữ liệu gồm:
  • Dòng đầu chứa hai số nguyên $n$ và $k$ là số quả mìn và bán kính lan nổ.
  • $n$ dòng tiếp theo, dòng thứ $i$ chứa ba số nguyên $x_i$, $y_i$, $t_i$.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra trên một dòng số giây nhỏ nhất để mọi quả mìn đều đã nổ.

Ràng buộc

• $1\le q\le {10}^4$
• $1\le n\le 2·{10}^5$, $0\le k\le {10}^9$
• $-{10}^9\le x_i,y_i\le {10}^9$, $0\le t_i\le {10}^9$
• Các quả mìn có toạ độ đôi một khác nhau.
• Tổng $n$ trên mọi bộ dữ liệu không vượt quá $2·{10}^5$.

Ví dụ