2. Классы подобия треугольников

Вам дан набор из $n$ треугольников ($1 \leq n \leq 1\:000\:000$). Каждый треугольник задается тремя целыми числами $-$ длинами его сторон. Длины сторон $-$ положительные целые числа, не превосходящие $10^9$. Некоторые пары треугольников подобны. В силу свойств подобия известно, что все эти треугольники распадаются на несколько классов, в каждом из которых все треугольники подобны друг другу. К примеру, три треугольника со сторонами $(6, 6, 10)$, $(15, 25, 15)$, $(35, 21, 21)$ все попарно подобны друг другу, то есть образуют один класс. Необходимо найти количество классов подобия, на которые распадаются данные $n$ треугольников.

Сложность алгоритма должна в среднем линейно зависеть от $n$ (может еще зависеть от ограничений на стороны треугольника). Т.е. никаких сортировок длинных массивов в решении делать нельзя.

В первой строке входа дано число $n$. В каждой из следующих $n$ строк $-$ по три целых числа, задающих стороны очередного треугольника.

Выведите число классов подобия.