Ваня построил бесконечное бинарное дерево по следующему правилу:

• В корне находится число 1 / 1;
• Левый сын вершины p / q будет иметь значение p / (p + q);
• Правый сын вершины p / q будет иметь значение (p + q) / q.

На рисунке вы можете видеть три верхних уровня дерева:

Затем Ваня пронумеровал вершины дерева сверху вниз по схеме, указанной на рисунке (следите за стрелочкой). Обозначим через F(i) i-ю дробь дерева, тогда первые его элементы будут иметь следующие значения: $$$F(1) = 1/1, F(2) = 1/2, F(3) = 2/1, F(4) = 1/3, F(5) = 3/2, F(6) = 2/3$$$.

Ваня придумал интересную задачу. Дано число $$$N$$$. Нужно найти дробь $$$p/q$$$, которой соответствует значение $$$F(N)$$$.