Bến xe khách liên tỉnh XYZ có điểm đỗ đón xe khách cập bến để hành khách xuống xe. Các điểm đỗ được đánh số từ đến . Ban điều hành bến xe nhận được yêu cầu cập bến của một dòng xe gồm xe khách chờ được phục vụ cập bến, lần lượt xe này sau xe kia. Các xe khách được đánh số từ đến theo thứ tự chờ được phục vụ. Xe khách thứ chỉ chấp nhận cập bến, nếu như nó được xếp phục vụ tại một trong các điểm đỗ có chỉ số trong khoảng từ đến và đồng thời tại điểm đỗ được bố trí để phục vụ nó chưa có xe nào trong số các xe (trong dòng xe đang xét) đến trước đã cập bến tại đó. Nếu có một xe khách đến lượt được phục vụ mà Ban điều hành không tìm được điểm đỗ theo đúng yêu cầu để phục vụ nó, thì xe này và tất cả các xe đến sau nó sẽ đồng loạt di chuyển sang bến xe khác và việc phục vụ dòng xe chấm dứt tại đây.
Yêu cầu: Hãy giúp Ban điều hành bến xe xác định số lượng lớn nhất các xe khách trong dòng xe mà bến xe khách XYZ có thể phục vụ đáp ứng các điều kiện đã nêu.
Dữ liệu vào:
Dòng đầu tiên chứa số nguyên là số lượng test. Tiếp đến là nhóm dòng, mỗi nhóm là thông tin về một test theo khuôn dạng sau đây:
Dòng đầu chứ hai số tương ứng là số lượng điểm đỗ trong bến xe và số lượng xe trong dòng xe yêu cầu được phục vụ;
Dòng thứ trong số dòng tiếp theo mô tả yêu cầu của xe khách thứ gồm hai số nguyên và mô tả khoảng chỉ số của các điểm đỗ trong bến xe mà xe khách thứ chấp nhận được phục vụ tại đó. Hai số trên cùng dọng được ghi cách nhau bởi dấu cách.
Dữ liệu ra:
Ghi ra dòng, mỗi dòng ghi số lượng xe khách lớn nhất trong dòng xe mà bến xe khách XYZ có thể phục vụ là câu trả lời cho test tương ứng trong dữ liệu vào.
Giới hạn:
Subtask ;
Subtask ;
Subtask ;
Subtask .
Ví dụ:
Dữ liệu vào:
1
4 3
1 4
1 1
1 1
Dữ liệu ra:
2
Dữ liệu vào:
1
4 6
1 2
1 2
1 3
1 3
2 4
1 4
Dữ liệu ra:
3
Giải thích:
Trong ví dụ thứ nhất: Xếp xe khách thứ nhất vào một trong các điểm điểm , xếp xe thứ hai vào điểm (duy nhất), xe thứ cũng yêu cầu xếp vào điểm nên không thể đáp úng được.
Trong ví dụ thứ hai: Xếp xe thứ và thứ vào hai điểm , xe thứ vào điểm , xe thứ không đáp ứng được nữa.
