Tập con đoạn thẳng lồng nhau

Cho $n$ đoạn thẳng trên trục số. Đoạn thứ $i$ có hai đầu mút $l_i$ và $r_i$, gồm tất cả các điểm $x$ thoả mãn $l_i\le x\le r_i$.

Hãy chọn ra một tập con có nhiều đoạn nhất sao cho với mọi cặp đoạn trong tập con đó, hoặc hai đoạn không có điểm chung, hoặc một đoạn nằm hoàn toàn bên trong đoạn còn lại.

Hai đoạn $[l_i;r_i]$ và $[l_j;r_j]$ được gọi là không có điểm chung nếu chúng không cùng chứa bất kỳ điểm nào. Ví dụ, cặp $[1;2]$ và $[3;4]$, cặp $[1;3]$ và $[5;5]$ là không có điểm chung; trong khi cặp $[1;2]$ và $[2;3]$, cặp $[1;2]$ và $[2;2]$ vẫn có điểm chung (điểm $2$), nên không được chọn cả hai.

Đoạn $[l_i;r_i]$ nằm trong đoạn $[l_j;r_j]$ nếu $l_j\le l_i$ và $r_i\le r_j$. Ví dụ, các đoạn $[2;2]$, $[2;3]$, $[3;4]$, $[2;4]$ đều nằm trong đoạn $[2;4]$, còn $[2;5]$ và $[1;4]$ thì không.

Bạn cần trả lời $t$ bộ dữ liệu độc lập.

Dữ liệu vào

• Dòng đầu chứa số nguyên $t$: số bộ dữ liệu.
• Với mỗi bộ dữ liệu:
  • Dòng đầu chứa số nguyên $n$: số đoạn thẳng.
  • $n$ dòng tiếp theo, dòng thứ $i$ chứa hai số nguyên $l_i$ và $r_i$.

Trong cùng một bộ dữ liệu, không có hai đoạn nào trùng nhau hoàn toàn.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra trên một dòng số đoạn nhiều nhất có thể chọn.

Ràng buộc

• $1\le t\le 1000$
• $1\le n\le 3000$
• $1\le l_i\le r_i\le 2·{10}^5$
• Tổng $n$ trên tất cả các bộ dữ liệu không vượt quá $3000$.

Ví dụ