Задача E. Прямые ≡

Условие

Даны n прямых на плоскости. Ваша задача — выбрать максимально возможное подмножество этих прямых так, чтобы среди выбранных прямых не было одинаковых прямых, параллельных прямых, прямых имеющих один и тот же y пересечения с прямой x = 0.

Формат входного файла

На первой строке количество тестов T, далее идёт описание T тестов. Первая строка теста содержит количество прямых n. Каждая из следующих n строк содержит по три целых числа A_i, B_i и C_i, описывающих прямую, как множество точек (x, y), для которых A_i x + B_i y + C_i = 0. Сумма n по всем тестам не превосходит 3000.

Формат выходного файла

Для каждого теста на одной строке выведите k — максимальный размер подмножества прямых. На следующей строке k целых чисел от 1 до n — номера выбранных прямых в произвольном порядке. Прямые нумеруются от 1 в том порядке, в котором даны в описании теста. Если существует несколько оптимальных решений, выведите любое одно.

Ограничения

1 ≤ n ≤ 3000

 − 10⁹ ≤ A, B, C ≤ 10⁹, A² + B² > 0

Примеры тестов

2
2
1 1 0
1 1 1
2
-1 1 1
-2 1 1

1
1
1
1