MDOLLS - VNOI

MDOLLS - Nested Dolls

Giới hạn

Thời gian: 0.259s
Bộ nhớ: 1536MB
Mã nguồn: 50000 bytes

Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.

Link đọc đề trên VNOJ

"Dilworth" có một bộ sưu tập các con búp bê Nga. Búp bê với chiều rộng w1 và chiều cao h1 sẽ nằm trong được con lật đật chiều rộng w2 và chiều cao h2 nếu w1 < w2 và h1 < h2. Tính số lớp búp bê bao nhau ít nhất mà có thể tạo ra được từ các búp bê ban đầu.

Input

Dòng đầu là số test, 1 ≤ t ≤ 20.

Mỗi test gồm:

số nguyên m, 1 ≤ m ≤ 20000, số lượng búp bê ban đầu.
Dòng tiếp theo là 2m số nguyên w1, h1,w2, h2, ... ,wm, hm, là chiều rộng và chiều cao của con búp bê thứ i, 1 ≤ wi, hi ≤ 10000.

Output

Ghi số lớp búp bê bao nhau ít nhất có thể trên một dòng cho từng test.

SAMPLE INPUT
4
3
20 30 40 50 30 40
4
20 30 10 10 30 20 40 50
3
10 30 20 20 30 10
4
10 10 20 30 40 50 39 51

SAMPLE OUTPUT
1
2
3
2

Người up: vdmedragon
Nguồn bài: Nordic 2007