N. Самая длинная цепочка

Цепочка Коллатца строится так: если число чётное, делим его на два, если нечётное — умножаем на три и прибавляем единицу. Цепочка заканчивается, когда доходит до единицы. Длина цепочки — количество чисел в ней, включая начальное и единицу.

Например, для 6: $6 \to 3 \to 10 \to 5 \to 16 \to 8 \to 4 \to 2 \to 1$, длина 9.

Найдите число от 1 до $N$, у которого цепочка самая длинная. Если таких чисел несколько, выведите наименьшее.

Без запоминания это слишком медленно: цепочки сильно перекрываются. Заметьте, что промежуточные числа могут вылезать за $N$ — запоминать их всё равно полезно, но массив для этого не подойдёт.

Одна строка содержит число $N$ ($1 \le N \le 10^6$).

Два числа через пробел: искомое число и длина его цепочки.