Вам даны \(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\) независимых наборов тестовых данных.
Выходные данные
Для каждого набора тестовых данных выведите ответ: максимально возможный размер такого подмножества заданного множества отрезков, что каждая пара отрезков в этом подмножестве либо не пересекается, либо же один из них лежит внутри другого.