F. Независимость парабол
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дан набор из $$$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$$$, которое содержит $$$f_i$$$ в качестве элемента.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$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$$$.

Пример
Входные данные
3
4
1 2 -1
-3 0 -3
-1 4 -5
1 2 -4
5
3 0 0
1 0 -5
-3 0 0
-1 0 10
1 0 -10
5
884 -667 497
680 -973 213
23 -548 -412
826 359 -333
773 212 218
Выходные данные
3 2 3 3
3 3 2 2 3
3 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$$$.