CF134B Pairs of Numbers

重题请做P2090

让我们假设有一对数$(a,b)$。我们可以从前一步得到后一对数$(a+b,b)$或者$(a,a+b)$。 让我们规定一开始这对数为$(1,1)$。你的任务就是找到数$k$，使$k$为从$(1,1)$转换到一对至少含有一个$n$的数对的最少步骤。

输入只包括一个整数$n(1

输出唯一的整数$k$。

The pair (1,1) can be transformed into a pair containing 5 in three moves: (1,1) $ → $ (1,2) $ → $ (3,2) $ → $ (5,2).