CF2195F.Parabola Independence

You are given a set of $n$ quadratic functions $F={f_1,f_2,\ldots,f_n }$, where $f_i(x)=a_i x^2 + b_i x + c_i$.

Two functions $f$ and $g$ are called independent if $f(x) \neq g(x)$ for all $x \in \mathbb{R}$.

Also, a set of functions $G={g_1,g_2,\ldots,g_k}$ is called organized if the two functions $g_i$ and $g_j$ are independent for all $1 \le i \lt j \le |G|$.

For each $i=1,2,\ldots,n$, please find the size of the largest organized subset of $F$ that contains $f_i$ as an element.

给定一组 $n$ 个二次函数 $F = \{f_1, f_2, \ldots, f_n\}$，其中 $f_i(x) = a_i x^2 + b_i x + c_i$。

若对所有 $x \in \mathbb{R}$ 均有 $f(x) \neq g(x)$，则称两个函数 $f$ 和 $g$ 是独立的。

此外，若对所有 $1 \le i < j \le |G|$，函数 $g_i$ 与 $g_j$ 均独立，则称函数集合 $G = \{g_1, g_2, \ldots, g_k\}$ 是有序的（organized）。

对每个 $i = 1, 2, \ldots, n$，请找出包含 $f_i$ 的 $F$ 的最大有序子集的大小。

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

The first line of each test case contains a single integer $n$ ($1 \le n \le 3000$).

Each of the $n$ following lines contains three integers $a_i$, $b_i$, $c_i$ denoting the function $f_i$ ($-10^6 \le a_i, b_i, c_i \le 10^6$, $a_i \neq 0$).

It is guaranteed that the functions in one test case are pairwise distinct.

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

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 3000$）。

接下来的 $n$ 行中，每行包含三个整数 $a_i$、$b_i$、$c_i$，表示函数 $f_i$（其中 $-10^6 \le a_i, b_i, c_i \le 10^6$，且 $a_i \neq 0$）。

保证同一测试用例中的所有函数两两不同。

保证所有测试用例的 $n^2$ 之和不超过 $3000^2$。

For each test case, output $n$ integers $s_1,s_2,\ldots,s_n$, where $s_i$ is the size of the largest organized subset that contains $f_i$.

对于每个测试用例，输出 $n$ 个整数 $s_1,s_2,\ldots,s_n$，其中 $s_i$ 是包含 $f_i$ 的最大有序子集的大小。

In the first test case, the functions are as follows:

• $f_1(x)=x^2+2x-1$;
• $f_2(x)=-3x^2-3$;
• $f_3(x)=-x^2+4x-5$;
• $f_4(x)=x^2+2x-4$.

The functions' graphs are as shown below:

The largest organized subsets of $F$ containing each function are as follows:

• ${f_1,f_3,f_4}$ is the largest organized subset that contains $f_1$;
• ${f_1,f_2}$ is the largest organized subset that contains $f_2$;
• ${f_1,f_3,f_4}$ is the largest organized subset that contains $f_3$;
• ${f_1,f_3,f_4}$ is the largest organized subset that contains $f_4$.

在第一个测试用例中，函数如下：

• $f_1(x)=x^2+2x-1$；
• $f_2(x)=-3x^2-3$；
• $f_3(x)=-x^2+4x-5$；
• $f_4(x)=x^2+2x-4$。

这些函数的图像如下所示：

包含每个函数的 $F$ 的最大有序子集如下：

• $\{f_1,f_3,f_4\}$ 是包含 $f_1$ 的最大有序子集；
• $\{f_1,f_2\}$ 是包含 $f_2$ 的最大有序子集；
• $\{f_1,f_3,f_4\}$ 是包含 $f_3$ 的最大有序子集；
• $\{f_1,f_3,f_4\}$ 是包含 $f_4$ 的最大有序子集。