2428. Forever...?

单点时限: 3.0 sec

内存限制: 256 MB

Forever Quest IX, a new, hot and very popular role-playing game like Neverending Fantasy, is out at August 2nd of 2008. Fans are looking forward to a new title of Forever Quest.

Johnny who becomes 12 years old is in trouble again. He bought Forever Quest IX and tried to reach the end of the game before his friend attained it. However, he cannot solve the first riddle in this game. Forever Quest is famous in extremely hard riddle like Neverending Fantasy. The first riddle is shown in the next paragraph.

At a town in this game, a great energy amplification system was developed. In this town, energy is held by an energy ball with exactly 1 energy, imagine a battery in the real world. This system takes one energy ball at a time and amplifies its energy to (1 + 1/n ) n. And then, amplified energy is charged to an external energy battery. Of course, the input energy ball is lost in this process. The parameter n can be set to any value greater than 1. In this town, therefore, n is set to infinity. However, there is a drawback in this system. To use energy charged to the external battery, we need energy balls. In case of the external battery holds e energy, you can get b ( e - 1 < b <= e) energy balls and remaining energy e - b is lost. For example, about 2.718 energy is charged in the external battery, you can get 2 energy balls and you lost remaining 0.718 energy. Moreover, you can get energy balls from an external battery only once because of a legal restriction. What is worse, you need to pay very heavy tax based on lost energy. And now, you have m energy balls, and input some or all of them to the system to get more energy balls. You should find the number of energy balls that you input to the system, to minimize lost energy when you get energy balls from the external battery.

Your job is to write a program to solve this riddle and help Johnny.

输入格式

Input consists of multiple test cases. Each test case consists of sigle line containing single positive integer m ( m < 231). Input is terminated by a case of m = 0, and it should not be processed.

输出格式

For each test case, you should output how many times should he breeds. If there are two or more solutions, you should output the smallest one.

样例

Input
1
0
Output
1

0 人解决,0 人已尝试。

0 份提交通过,共有 0 份提交。

9.9 EMB 奖励。

创建: 12 年,10 月前.

修改: 4 年前.

最后提交: N/A.

来源: International Maximum-Cup 2008

题目标签