Maximum Number of Squares

Time limit2sMemory limit128 MB

Summary

Given N points on a plane, place them to maximize the number of axis-aligned squares whose four vertices are chosen points.

Level: Hard8 of 10
Topics: Math, Combinatorics, Geometry, Brute force
Solved: No attempts yet

Problem

Place N distinct points on a two-dimensional plane. A square is counted when its four vertices are among the chosen points and every side is parallel to one of the coordinate axes.

The same square is counted only once; squares with different positions or side lengths are distinct.

Given N, find the maximum possible number of such squares.

Input

The first line contains an integer N. It satisfies 0 <= N <= 1,000,000.

Output

Print the maximum possible number of squares on the first line.

Examples5

Example 1
Input
```
16
```
Expected output
```
14
```
Example 2
Input
```
4
```
Expected output
```
1
```
Example 3
Input
```
5
```
Expected output
```
1
```
Example 4
Input
```
6
```
Expected output
```
2
```
Example 5
Input
```
115
```
Expected output
```
340
```