In 1850, the Reverend Thomas P. Kirkman, a clergyman of the Church of England, proposed an interesting problem known as the schoolgirl walking problem. In a certain girls' school, there were $15$ schoolgirls in a group. They went for a walk outside the school every day. To strengthen their mutual understanding and promote friendship, Kirkman envisioned that if the girls were appropriately divided into $5$ groups of $3$ girls each, such that every girl could be in the same group with every other girl exactly once within $7$ days, how should they be grouped to achieve this?

This seemingly simple problem has an unusual grouping algorithm, which later became known as the Kirkman's schoolgirl problem. Over a hundred years later, many other interesting grouping algorithms for schoolgirl walks were invented. One such interesting random circular grouping algorithm is described as follows:

Suppose there are $n$ schoolgirls to be grouped. First, randomly assign a unique number to each girl. The set of numbers for these $n$ girls is exactly $[1, n]$. Girls in the same group can freely sit in a circle on the grass. Each girl in the circle must satisfy the condition that the product of her number and the numbers of her two neighbors is less than $n$. When there is only one girl in the circle, her own number must be less than $n$. Girls who satisfy the above conditions are placed in one group. The remaining girls continue to be grouped using this method.

Schoolgirl Walking Problem: For a given integer $n$, calculate the maximum number of girls that can be placed in the same group.

Input

The input contains multiple test cases. Each line contains an integer $n$, representing the number of schoolgirls to be grouped.

Output

For each test case $n$ in the input file, output the maximum number of girls that can be placed in the same group. Each result should be printed on a new line.

Examples

Input 1

2
3
5
7
8

Output 1

1
2
2
3
3

Subtasks

Note

1. The number of test cases was not provided during the contest; "participants should evaluate this themselves."
2. The description in the problem is ambiguous, but no clarification was provided during the contest.