URI Online Judge | 1444

Drakes' Racing

By Lucas Hermann Negri, UDESC Brasil
Timelimit: 3

Pirabeiraba is a district of Joinville, where german settlers installed themselves at the start of the 20th century. Annually there is the cassava party, a tuber that is also known as macaxeira in the brazilian northeast region. To accompany the cassava, there's nothing like a traditional germanic dish: the stuffed drake! For the culinary experts, there is a magic in this combination: drake with cassava. However, to kill the drake, you must capture him while his blood is very warm. For that, the drake must be tired. People say that his warm blood is synonymous with fertility, in other words: an aphrodisiac! But that's for another story.

In this game of chasing the drake, an idea came of tiring them with a race between themselves. The physical space of the Society Rio da Prata is limited, because of that they built only three lanes to do these races. The races are made with groups of two and three drakes. The drakes who gets the first places on the races are then arranged again in groups of 2 or 3 for another round. This goes on until there's only one drake left, the champion, which escapes from the saucepan (for now) as a prize. All the surviving drakes must race in the round, that is, if it's not possible to split all the drakes in groups of three, some groups of two must be formed in order to minimize the number of races. Examples are seen in the Figure 1.

Figure 1: Examples: competition with 4, 5 and 6 drakes.

The losing drakes will be the first to go to the saucepan. You were invited to eat drake with cassava, but in exchange you must write a program that calculates the number of races that must be made to determinate the champion drake.

Input

The program input is composed by various test cases. Each test case is composed by a line containing an integer n, where 0 ≤ n ≤ 100,000, and where n = 0 is used solely to mark the end of the input, which must be disconsidered.

Output

Your program must print in the standard output a line per test case, containing the number of races needed to choose the champion drake.

Sample Input Sample Output

3
4
5
6
0

1
3
3
3