Vườn cây

Bờm vừa thắng cược Phú Ông và phần thưởng là lấy tất cả các cây gỗ sưa trong vườn của Phú Ông. Thấy Phú Ông thẫn thờ vì mất cây, Bờm liền đưa cho Phú Ông một sợi dây và nói: "Ông hãy chọn một số cây, những cây còn lại tôi sẽ lấy đi, chú ý rằng, sau khi tôi lấy cây đi thì những cây còn lại phải bao được bằng sợi dây này". Phú Ông đồng ý ngay và tìm cách chọn cây sao cho giữ lại được nhiều cây nhất. Giả sử vườn cây của Phú Ông có $n$ cây và coi mỗi cây như một hình tròn trên mặt phẳng, các cây có cùng bán kính $r$, cây thứ $i$ có tọa độ tâm $(x_i,y_i)$.

Các cây được giữ lại bao được bằng sợi dây nếu có thể căng sợi dây thành một đường khép kín có độ dài không vượt quá $d$ sao cho mọi hình tròn của các cây đó đều nằm bên trong (hoặc chạm vào) đường khép kín này. Phú Ông có thể không giữ lại cây nào.

Yêu cầu: Cho $d$ là độ dài sợi dây và tọa độ tâm của $n$ cây, các cây có bán kính $r$. Hãy giúp Phú Ông tìm cách chọn để giữ lại nhiều cây nhất.

Dữ liệu vào

Dòng đầu tiên ghi số nguyên dương $K$ là số lượng bộ dữ liệu. Tiếp đến là $K$ nhóm dòng, mỗi nhóm tương ứng với một bộ dữ liệu có cấu trúc như sau:

• Dòng thứ nhất ghi ba số nguyên dương $d$, $n$ và $r$ ($d\le {10}^9$; $r\le 100$);
• $n$ dòng tiếp theo, dòng thứ $i$ chứa hai số nguyên $x_i,y_i$ ($|x_i|,|y_i|\le 1000$).

Dữ liệu đảm bảo các hình tròn không giao nhau (hai hình tròn có thể tiếp xúc nhau, tức là khoảng cách giữa hai tâm bất kỳ không nhỏ hơn $2r$). Các số trên cùng một dòng được ghi cách nhau ít nhất một dấu cách.

Dữ liệu ra

Gồm $K$ dòng, mỗi dòng ghi một số nguyên là số lượng cây mà Phú Ông có thể giữ lại được tương ứng với bộ dữ liệu.

Ràng buộc

• $1\le K\le 20$.
• $1\le n\le 10$ trong mỗi bộ dữ liệu.
• $1\le d\le {10}^9$; $1\le r\le 100$.
• $|x_i|,|y_i|\le 1000$; khoảng cách giữa hai tâm bất kỳ không nhỏ hơn $2r$.

Subtasks

• Subtask 1 ($15$ điểm): $n\le 2$.
• Subtask 2 ($15$ điểm): $n\le 3$.
• Subtask 3 ($20$ điểm): $n\le 4$.
• Subtask 4 ($20$ điểm): $n\le 10$.

Ví dụ