WonderTeam

Time limit1sMemory limit128 MB

Summary

For each n, find the largest possible rank a team can reach while strictly leading the league in wins, goals scored, and fewest goals conceded in a double round-robin.

Level: Medium7 of 10
Topics: Greedy, Math, Combinatorics, Simulation
Solved: No attempts yet

Statement

The Brasileiro Championship features $n$ football teams. Every team plays every other team twice — once at home and once away. A win is worth 3 points, a draw gives each of the two teams 1 point, and a loss is worth 0 points.

When all matches are over, the teams are ranked by their total points. The rank of a team with $p$ points is defined as one plus the number of teams that have strictly more than $p$ points, so several teams may share the same rank.

Besides the champion (the team or teams ranked first), a WonderTeam is also selected whenever one exists. A WonderTeam is a team that satisfies all three of the following conditions, and satisfies each of them strictly (no other team ties its value):

it has the strictly highest number of wins,
it has scored the strictly highest number of goals,
it has conceded the strictly lowest number of goals.

A WonderTeam is defined only when a single team satisfies all three conditions strictly.

Determine the worst (that is, the largest) rank a WonderTeam can possibly have.

Input

The input consists of several test cases. Each test case is a single line containing $n$ ( $1 \le n \le 50$ ), the number of teams in the league. The input ends with a line containing $0$ .

Output

For each test case, print on its own line the worst possible rank of the WonderTeam.

Examples5

Example 1
Input
```
1
3
0
```
Expected output
```
1
1
```
Example 2
Input
```
1
0
```
Expected output
```
1
```
Example 3
Input
```
2
0
```
Expected output
```
1
```
Example 4
Input
```
4
0
```
Expected output
```
2
```
Example 5
Input
```
1
2
3
4
5
0
```
Expected output
```
1
1
1
2
5
```