欧几里德最差序列 ## 题目描述 欧几里德算法是数论中求两个正整数最大公约数的有效算法。对大部分正整数对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 最后求得的最大公约数为1。 ``` 在本题中，由这些正整数构成的序列称为欧几里德算法最差序列（按从小到大排列）。给定正整数n，输出该序列中的第n个数。 ## 输入描述 输入文件中包含多个测试数据。每个测试数据占一行，为一个正整数n，n≤40。输入文件最后一行为0，代表输入结束。 ## 输出描述 对每个测试数据，输出欧几里德算法最差序列中的第n个数。 ## 样例输入 ```txt 1 2 9 0 ``` ## 样例输出 ```txt 1 2 55 ```