CF2249A.Rank Subsequence

You are given $n$ elements arranged in a line, numbered $1, 2, \ldots, n$ from left to right.

You may delete any number of elements (possibly none). The remaining elements form a subsequence and keep their relative order. Let the length of this subsequence be $m$. If the element with original index $i$ becomes the $j$-th element of the subsequence ($1 \le j \le m$), define

• its left rank as $j$, and
• its right rank as $m - j + 1$.

For each element, you are given two integer segments $[l_i, r_i]$ and $[u_i, v_i]$. The $i$-th element is valid in a subsequence of length $m$ if and only if, when it occupies position $j$ in that subsequence, both of the following hold:

• Its left rank is not in the range $[l_i, r_i]$ (i.e., $j \notin [l_i, r_i]$);
• Its right rank is not in the range $[u_i, v_i]$ (i.e., $m - j + 1 \notin [u_i, v_i]$).

A subsequence is valid if every element remaining in it is valid.

Find the maximum possible length of a valid subsequence. The answer may be $0$.

给你 $n$ 个元素，从左到右依次编号为 $1, 2, \ldots, n$。

你可以删除任意数量的元素（也可以一个都不删）。剩余元素构成一个子序列，并保持其原有相对顺序。设该子序列的长度为 $m$。若原编号为 $i$ 的元素在该子序列中处于第 $j$ 个位置（$1 \le j \le m$），则定义：

• 它的左秩为 $j$；
• 它的右秩为 $m - j + 1$。

对每个元素 $i$，给定两个整数区间 $[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$。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 5000$). The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1\le n\le 5000$) — the number of elements.

Then $n$ lines follow, the $i$-th line containing the four integers $l_i$, $r_i$, $u_i$, and $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$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $5000$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $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$。

For each test case, print one integer — the maximum possible length of a valid subsequence.

对于每个测试用例，输出一个整数——有效子序列的最大可能长度。

In the first test case, the only element cannot form a valid subsequence of length $1$, so the answer is $0$.

In the second test case, all $4$ elements can be kept. Their pairs of left and right ranks are $(1, 4)$, $(2, 3)$, $(3, 2)$, and $(4, 1)$, respectively, and all of them are valid.

In the third test case, one optimal choice is to keep the elements with original indices $2$, $3$, and $5$.

In the fourth test case, keeping both elements yields a valid subsequence of length $2$. Note that no valid subsequence of length $1$ exists.

In the fifth test case, one optimal choice is to keep the elements with original indices $3$, $4$, and $5$.

在第一个测试用例中，唯一的一个元素无法构成长度为 $1$ 的有效子序列，因此答案为 $0$。

在第二个测试用例中，全部 $4$ 个元素均可保留。它们对应的左右排名对分别为 $(1, 4)$、$(2, 3)$、$(3, 2)$ 和 $(4, 1)$，且全部有效。

在第三个测试用例中，一种最优选择是保留原始下标为 $2$、$3$ 和 $5$ 的元素。

在第四个测试用例中，保留两个元素可得到一个长度为 $2$ 的有效子序列。注意：不存在长度为 $1$ 的有效子序列。

在第五个测试用例中，一种最优选择是保留原始下标为 $3$、$4$ 和 $5$ 的元素。