有一天，又是小明他闲的没事在家里玩翻硬币的游戏。这个游戏是有N个硬币正面朝上排成一排，如果N为偶数每次将任意N-1个硬币翻过来放在原位置；如果N为奇数每次将任意N-2个硬币翻过来放在原位置，不断地重复上述过程，直到最后全部硬币翻成反面朝上为止。小明想要用最少的步数赢得游戏。请你设计程序让计算机输出最少的翻币次数。
Input
输入多组数据，每组输入一个整数N（2<=N<10^9），当N为0时结束程序，不处理。
Output
对于每个输入案例，输出一个整数表示最少的翻币次数。
SampleInput
2
3
0
SampleOutput
2
3
