Description

As a return for making the PPT, classmate XHY decides to send some “warmth” to CYD dashen—a set of answers to an English newspaper. This newspaper is an $N \times N$ grid, where some cells contain answers. The distribution seems regular: for cell $(x, y)$, it contains an answer if and only if $x$ and $y$ are not coprime.

XHY’s phone can capture one $1 \times 2$ region per photo (either horizontal or vertical). Please write a program to find the minimum number of photos required to capture all the answers and send them to CYD dashen.

Input Format

One line, a positive integer $N$.

Output Format

One line, a non-negative integer representing the minimum number of photos required.

4

5

5

6

6

11

Hint

Constraints:

• For 30% of the testdata, $N \le 10$.
• For 60% of the testdata, $N \le 50$.
• For 100% of the testdata, $1 \le N \le 233$.

Translated by ChatGPT 5