A. Ранговая подпоследовательность
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам даны $$$n$$$ элементов, расположенных в линию и пронумерованных слева направо $$$1, 2, \ldots, n$$$.

Вы можете удалить любое количество элементов (возможно, ни одного). Оставшиеся элементы образуют подпоследовательность и сохраняют свой относительный порядок. Пусть длина этой подпоследовательности равна $$$m$$$. Если элемент с исходным индексом $$$i$$$ становится $$$j$$$-м элементом подпоследовательности ($$$1 \le j \le m$$$), определим

  • его левый ранг как $$$j$$$;
  • его правый ранг как $$$m - j + 1$$$.

Для каждого элемента заданы два отрезка целых чисел $$$[l_i, r_i]$$$ и $$$[u_i, v_i]$$$. $$$i$$$-й элемент является корректным в подпоследовательности длины $$$m$$$ тогда и только тогда, когда, если он занимает позицию $$$j$$$ в этой подпоследовательности, выполняются оба условия:

  • его левый ранг не принадлежит отрезку $$$[l_i, r_i]$$$ (то есть $$$j \notin [l_i, r_i]$$$);
  • его правый ранг не принадлежит отрезку $$$[u_i, v_i]$$$ (то есть $$$m - j + 1 \notin [u_i, v_i]$$$).

Подпоследовательность называется корректной, если каждый оставшийся в ней элемент является корректным.

Найдите максимальную возможную длину корректной подпоследовательности. Ответ может быть равен $$$0$$$.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 5000$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

В первой строке каждого набора входных данных дано одно целое число $$$n$$$ ($$$1\le n\le 5000$$$) — количество элементов.

Затем следуют $$$n$$$ строк, $$$i$$$-я строка содержит четыре целых числа $$$l_i$$$, $$$r_i$$$, $$$u_i$$$ и $$$v_i$$$ ($$$1\le i\le n$$$, $$$1\le l_i\le r_i\le n$$$, $$$1\le u_i\le v_i\le n$$$).

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$5000$$$.

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

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

Пример
Входные данные
5
1
1 1 1 1
4
2 2 2 2
1 1 1 1
1 1 1 1
1 1 2 2
5
1 1 3 3
2 2 2 2
3 3 1 1
1 5 1 5
5 5 5 5
2
2 2 1 1
1 1 2 2
6
1 1 6 6
1 2 5 6
2 3 4 5
3 4 3 4
4 5 2 3
5 6 1 2
Выходные данные
0
4
3
2
3
Примечание

В первом наборе входных данных единственный элемент не может образовать корректную подпоследовательность длины $$$1$$$, поэтому ответ равен $$$0$$$.

Во втором наборе входных данных можно оставить все $$$4$$$ элемента. Их пары левого и правого рангов равны $$$(1, 4)$$$, $$$(2, 3)$$$, $$$(3, 2)$$$ и $$$(4, 1)$$$ соответственно, и все они корректны.

В третьем наборе входных данных один из оптимальных вариантов — оставить элементы с исходными индексами $$$2$$$, $$$3$$$ и $$$5$$$.

В четвёртом наборе входных данных, если оставить оба элемента, получится корректная подпоследовательность длины $$$2$$$. Заметьте, что корректной подпоследовательности длины $$$1$$$ не существует.

В пятом наборе входных данных один из оптимальных вариантов — оставить элементы с исходными индексами $$$3$$$, $$$4$$$ и $$$5$$$.