F. Очередное подмножество отрезков
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам даны $$$n$$$ отрезков на координатной оси $$$OX$$$. $$$i$$$-й отрезок имеет границы $$$[l_i; r_i]$$$. Все точки $$$x$$$, для которых выполняется условие $$$l_i \le x \le r_i$$$, принадлежат $$$i$$$-му отрезку.

Ваша задача — выбрать такое максимальное по размеру (количеству отрезков) подмножество заданного множества отрезков, что каждая пара отрезков в этом подмножестве либо не пересекается либо же один из них лежит внутри другого.

Два отрезка $$$[l_i; r_i]$$$ и $$$[l_j; r_j]$$$ не пересекаются, если у них нет общих точек. Например, отрезки $$$[1; 2]$$$ и $$$[3; 4]$$$, $$$[1; 3]$$$ и $$$[5; 5]$$$ не пересекаются, а отрезки $$$[1; 2]$$$ и $$$[2; 3]$$$, $$$[1; 2]$$$ и $$$[2; 2]$$$ пересекаются.

Отрезок $$$[l_i; r_i]$$$ лежит внутри отрезка $$$[l_j; r_j]$$$, если $$$l_j \le l_i$$$ и $$$r_i \le r_j$$$. Например, отрезки $$$[2; 2]$$$, $$$[2, 3]$$$, $$$[3; 4]$$$ и $$$[2; 4]$$$ лежат внутри отрезка $$$[2; 4]$$$, а $$$[2; 5]$$$ и $$$[1; 4]$$$ — нет.

Вам необходимо ответить на $$$t$$$ независимых наборов тестовых данных.

Входные данные

Первая строка входных данных содержит одно целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов тестовых данных. Затем следуют $$$t$$$ наборов тестовых данных.

Первая строка набора тестовых данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 3000$$$) — количество отрезков. Следующие $$$n$$$ строк описывают отрезки. $$$i$$$-й отрезок задан двумя целыми числами $$$l_i$$$ и $$$r_i$$$ ($$$1 \le l_i \le r_i \le 2 \cdot 10^5$$$), где $$$l_i$$$ — левая граница $$$i$$$-го отрезка, а $$$r_i$$$ — правая граница $$$i$$$-го отрезка.

Дополнительное ограничение на входные данные: в заданном списке отрезков нет дубликатов.

Гарантируется, что сумма $$$n$$$ не превосходит $$$3000$$$ ($$$\sum n \le 3000$$$).

Выходные данные

Для каждого набора тестовых данных выведите ответ: максимально возможный размер такого подмножества заданного множества отрезков, что каждая пара отрезков в этом подмножестве либо не пересекается, либо же один из них лежит внутри другого.

Пример
Входные данные
4
4
1 5
2 4
2 3
3 4
5
1 5
2 3
2 5
3 5
2 2
3
1 3
2 4
2 3
7
1 10
2 8
2 5
3 4
4 4
6 8
7 7
Выходные данные
3
4
2
7