Time Limit: Java: 2000 ms / Others: 2000 ms
Memory Limit: Java: 65536 KB / Others: 65536 KB
In Zhejiang University, there is a famous BBS named Freecity. Usually we call it 88.
Recently some students at the Humour board on 88 create a new game - Swordsmanship. Different from the common sword fights, this game can be held with three players playing together in a match. Only one player advances from the match while the other two are eliminated. Sometimes they also hold a two-player match if needed, but they always try to hold the tournament with as less matches as possible.
The input contains several test cases. Each case is specified by one positive integer n (0 < n < 1000000000), indicating the number of players. Input is terminated by n=0.
For each test case, output a single line with the least number of matches needed to decide the champion.