Giải bài trực tuyến Học viện Công nghệ Bưu chính Viễn Thông

Công ty CE đã xây dựng một máy tô màu tự động (APM) để tô màu hoàn toàn một bảng bao phủ bởi các hình chữ nhật liền kề mà không chồng chéo lên nhau. Các hình chữ nhật này có thể có các kích thước khác nhau nhưng có màu cần tô được xác định trước.

Để tô màu bảng, APM có quyền lấy các bộ chổi với các màu khác nhau riêng biệt. APM lấy một chổi với màu C và tô tất cả các hình chữ nhật có màu C nhưng phải tuân thủ quy tắc: Một hình chữ nhật chỉ có thể được sơn nếu các hình chữ nhật ngay trên nó đã được sơn. Ví dụ như trong hình trên: Hình chữ nhật F chỉ có thể tô màu nếu hình chữ nhật C và D đã được tô màu. Chú ý: Khi tô màu một hình chữ nhật sẽ tô toàn bộ diện tích của hình chữ nhật, không được để trống lại.

Bạn đang viết chương trình cho APM để tô màu bảng đã cho sao cho số lần lấy chổi là tối thiểu. Chú ý: Nếu một chổi được lấy nhiều lần, thì tất cả các lần lấy sẽ được đếm.

Input

- Dòng đầu tiên chứa một số nguyên là số bộ test M (1<=M<=10).

- Mỗi bộ test có dạng như sau: Dòng đầu chứa số nguyên N, là số các hình chữ nhật. Sau đó là N dòng,  mỗi dòng gồm 5 số nguyên cách nhau bới dấu cách – đại diện cho một hình chữ nhật R - có ý nghĩa lần lượt là: y và x – tọa độ góc trên bên trái của R, tiếp y và x – tọa độ góc dưới bên phải của R, tiếp theo là mã màu của R.

- Chú ý:

• Mà màu là một số nguyên trong phạm vi 1..20
• Góc trên bên trái của bảng luôn có tọa độ (0,0)
• Các tọa độ trong phạm vi 0..99
• N nằm trong phạm vi 1..15

Output

Mỗi bộ test in trên một dòng số lần phải lấy chổi ít nhất có thể để tô màu

Example

Input:
1
7
0 0 2 2 1
0 2 1 6 2
2 0 4 2 1
1 2 4 4 2
1 4 3 6 1
4 0 6 4 1
3 4 6 6 2

Output:
3