Erwin trưng bày viên kim cương, viên thứ nằm tại tọa độ và có màu trong số màu có thể có. Để ăn trộm số kim cương này, Lupin đã chế tạo ra một thiết bị đặc biệt: một cánh tay robot có thể lấy kim cương mà không kích hoạt hệ thống báo động. Robot được sử dụng duy nhất một lần bằng cách như sau:
Chọn hai điểm và có cùng tung độ.
Hai tay robot sẽ ngắm đến hai điểm và .
Robot sẽ gắp toàn bộ các viên kim cương nằm phía dưới đoạn thẳng nối và (kể cả biên).
Xem hình minh họa dưới đây:
Để đảm bảo vụ trộm không bị phát hiện, Lupin đã chọn phương án an toàn: tập kim cương hắn sắp sửa lấy không chứa đủ màu.
Xác định xem Lupin có thể ăn trộm được nhiều nhất bao nhiêu viên kim cương?
Dữ liệu vào:
Dòng đầu tiên chứa một số nguyên dương là số lượng test. Mỗi bộ test được định dạng như sau:
Dòng đầu tiên chứa hai số nguyên và ;
dòng tiếp theo, mỗi dòng chứa ba số nguyên là tọa độ và màu của viên kim cương thứ . Mỗi màu sẽ có ít nhất một viên kim cương.
Dữ liệu ra:
Với mỗi test, in ra số lượng kim cương nhiều nhất có thể lấy được.
