C. Campfire Riddle
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

One day Yurik found himself in a forest near the campfire where $$$n$$$ people had gathered.

It turned out that some of them are friends. Let's number all people with integers from $$$1$$$ to $$$n$$$. Let's denote the number of people that are friends with the $$$i$$$-th person, as $$$d_i$$$. It suddenly turned out that two people with numbers $$$i$$$ and $$$j$$$ ($$$i \ne j$$$) are friends if and only if $$$d_i = d_j$$$.

When Yurik came home he got curious, what is the minimum number of pairs of people that could be friends, so that the condition described above to be satisfied?

Input

The only line contains one integer $$$n$$$ ($$$1 \le n \le 5\,000$$$) — the number of people.

Output

Print one integer — the minimum number of pairs of friends.

Examples
Input
4
Output
3
Input
5
Output
4
Note

Consider the first example. All possible cases are described below:

  1. Each two people are friends with each other. In this case the number of pairs of friends is $$$\frac{4 \cdot 3}{2} = 6$$$.
  2. Three people are pairwise friends with each other, and the fourth person is not friend with anyone. In this case the number of pairs of friends is $$$3$$$.