### 问题描述 欧几里德算法是数论中求两个正整数最大公约数的有效算法。对大部分正整数对 $m$ 和 $n$，欧几里德算法能经过短短几轮运算就能求得 $m$ 和 $n$ 的最大公约数。但是对于一些正整数对，如 $55$ 和 $34$，欧几里德算法的效率却得不到体现。例如，对 $55$ 和 $34$，欧几里德算法的执行过程如下： ```txt m = 55, n = 34 m = 34, n = 21 m = 21, n = 13 m = 13, n = 8 m = 8, n = 5 m = 5, n = 3 m = 3, n = 2 m = 2, n = 1 ``` 执行了 $9$ 次，最后求得的最大公约数为 $1$。 在本题中，由这些正整数构成的序列称为欧几里德算法最差序列（按从小到大排列）。给定正整数 $n$，输出该序列中的第 $n$ 个数。 ### 输入格式 输入数据占一行，为一个正整数 $n$，$n\le 40$。 ### 输出格式 输出占一行，为欧几里德算法最差序列中的第 $n$ 个数。 ### 样例输入1 ```txt 2 ``` ### 样例输出1 ```txt 2 ``` ### 样例输入2 ```txt 9 ``` ### 样例输出2 ```txt 55 ```