Nested Dolls

View as PDF
Submit solution
Points: 0.23 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout
Problem source:
Nordic 2007
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

"Dilworth" có một bộ sưu tập các con búp bê Nga. Búp bê với chiều rộng ~w_1~ và chiều cao ~h_1~ sẽ nằm trong được con búp bê chiều rộng ~w_2~ và chiều cao ~h_2~ nếu ~w_1 < w_2~ và ~h_1 < h_2~.

Tính số lớp búp bê bao nhau ít nhất mà có thể tạo ra được từ các búp bê ban đầu.

Input

Dòng đầu là số test ~(1 \le t \le 20)~.

Mỗi test gồm:

  • số nguyên ~m (1 \le m \le 20000)~, số lượng búp bê ban đầu.
  • Dòng tiếp theo là ~2m~ số nguyên ~w_1, h_1, w_2, h_2, ..., w_m, h_m~, là chiều rộng và chiều cao của con búp bê thứ ~i~ ~(1 \le w_i, h_i \le 10000)~.

Output

Ghi số lớp búp bê bao nhau ít nhất có thể trên một dò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

Comments

Please read the guidelines before commenting.


  • 0
    KiraYoshikage  commented on Feb. 4, 2024, 3:04 p.m.

    mn giải thích test mẫu vs :((


  • -14
    phongngutin  commented on Oct. 24, 2023, 7:01 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


  • -8
    huynhquocluatit10  commented on Oct. 24, 2023, 7:01 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


  • -10
    huynhquocluatit10  commented on Oct. 24, 2023, 7:00 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


  • -10
    kripper  commented on March 30, 2023, 7:47 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


  • -3
    dung134  commented on Jan. 7, 2023, 3:35 a.m.

    Em chưa hiểu test mẫu lắm. Mọi người có thể giải thích cho em được không ạ