This is the easy version of the problem. In this version, the constraints on $n$ and the time limit are lower. You can make hacks only if both versions of the problem are solved.
A set of (closed) segments is complex if it can be partitioned into some subsets such that
- all the subsets have the same size; and
- a pair of segments intersects if and only if the two segments are in the same subset.
You are given $n$ segments $[l_1, r_1], [l_2, r_2], \ldots, [l_n, r_n]$. Find the maximum size of a complex subset of these segments.
Input
Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^3$). The description of the test cases follows.
The first line of each test case contains a single integer $n$ ($1 \le n \le 2 \cdot 10^4$) — the number of segments.
The second line of each test case contains $n$ integers $l_1, l_2, \ldots, l_n$ ($1 \le l_i \le 2n$) — the left endpoints of the segments.
The third line of each test case contains $n$ integers $r_1, r_2, \ldots, r_n$ ($l_i \leq r_i \le 2n$) — the right endpoints of the segments.
It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^4$.
Output
For each test case, output a single integer: the maximum size of a complex subset of the given segments.
Note
In the first test case, all pairs of segments intersect, therefore it is optimal to form a single group containing all of the three segments.
In the second test case, there is no valid partition for all of the five segments. A valid partition with four segments is the following: $\{\{ [1, 5], [2, 4] \}, \{ [6, 9], [8, 10] \}\}$.
In the third test case, it is optimal to make a single group containing all the segments except the second.
样例
3
3
1 2 3
5 4 6
5
1 2 3 6 8
5 4 7 9 10
5
3 1 4 1 5
7 2 6 5 10
3
4
4
题面与样例版权归 Codeforces 及出题人所有；中文翻译由 AI 生成（CI 管线），如有出入请以原文为准。