Circle on Tiles

Time limit5sMemory limit128 MB

Summary
Given an even N, count how many unit tiles of an N by N grid are crossed by the circle inscribed tangent to all four sides.
Level

Medium6 of 10

Topics
Geometry, Math, Implementation
Solved
No attempts yet

Problem

Square tiles with side length 1 cm are placed without gaps to form a large square whose side length is N cm. N is even.

Draw a circle tangent to all four sides of the large square. Among the N \times N tiles in the square, determine how many tiles the circumference of the circle passes through.

Input

The first line contains an even integer N. (2 \le N \le 150,000,000)

Output

Print the number of tiles that the circumference of the circle passes through.

Examples2

  1. Example 1

    Input
    50
    Expected output
    180

  2. Example 2

    Input
    2
    Expected output
    4