I. Худший случай для Евклида

Найдите наименьшую пару чисел $a \ge b \ge 1$, на которой алгоритм Евклида делает ровно $k$ шагов. Шаг — это одно применение правила $\gcd(a, b) = \gcd(b, a \bmod b)$.

Наименьшая — значит, с наименьшим $a$, а среди таких с наименьшим $b$.

Ответ стоит сначала получить перебором для маленьких $k$ и посмотреть на него. Последовательность окажется знакомой — и это не совпадение: именно она заставляет Евклид работать дольше всего.

Одна строка содержит число $k$ ($1 \le k \le 85$).

Два числа через пробел — искомая пара.