Background

Special for beginners, ^_^

Description

过年了，爸爸妈妈分别给了小明一个压岁包，里面都有1·元钱。父母承诺，如果小明不花这两个压岁包，那么下一天，小明可以选择其中一个包交给父母，父母在这个包里面再放入和另一个包等量的钱后发还给小明。

小明决定当个守财奴，他希望其中一个包的金额变成n元，问最少需要经过多少天。

Format

Input

每行（不超过30行）一个正整数 n（<=1e6）。

Output

对于每个n，每行一个整数表示答案。

Samples

5
1

3
0

Limitation

1s, 1024KiB for each test case.