给你一套 $$$n$$$ 二次 函数 $$$F=\{f_1,f_2,\ldots,f_n \}$$$,其中 $$$f_i(x)=a_i x^2 + b_i x + c_i$$$。
调用了两个函数 $$$f$$$ 和 $$$g$$$ 独立 如果 $$$f(x) \neq g(x)$$$ 对于所有 $$$x \in \mathbb{R}$$$。
另外,调用了一组函数 $$$G=\{g_1,g_2,\ldots,g_k\}$$$ 组织 如果两个函数 $$$g_i$$$ 和 $$$g_j$$$ 对于所有 $$$1 \le i \lt j \le |G|$$$ 都是独立的。
对于每个 $$$i=1,2,\ldots,n$$$,请找到包含 $$$f_i$$$ 作为元素的 $$$F$$$ 的最大组织子集的大小。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$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$$$。
输出
对于每个测试用例,输出 $$$n$$$ 整数 $$$s_1,s_2,\ldots,s_n$$$,其中 $$$s_i$$$ 是包含 $$$f_i$$$ 的最大组织子集的大小。
示例
输入复制
341 2 -1-3 0 -3-1 4 -51 2 -453 0 01 0 -5-3 0 0-1 0 101 0 -105884 -667 497680 -973 21323 -548 -412826 359 -333773 212 218
输出复制
3 2 3 33 3 2 2 33 3 3 1 2
注意
第一个测试用例中,功能如下:
- $$$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$$$ 的最大组织子集。