Background

After enduring three years of junior high school, the "Learn English" newspaper still haunts me. When the first issue of "Learn English" for高一 floated in front of me, CYD the mastermind felt utterly绝望, yet he clung to a glimmer of hope—XHY always finished faster than him.

Problem Description

In return for making PPT, XHY decided to offer some "warmth" to CYD—the answers to an English newspaper. This newspaper is a $N \times N$ matrix, with answers in certain cells. The distribution of answers seems to follow a pattern: for cell $(x, y)$, there is an answer if and only if $x$ and $y$ are not coprime.

XHY's phone can capture a $1 \times 2$ area (either horizontally or vertically) at a time. Write a program to determine the minimum number of photos she needs to take to send all the answers to CYD.

Input Format

A single line containing a positive integer $N$.

Output Format

A single line containing a non-negative integer representing the minimum number of photos needed.

Sample Input and Output

Sample Input #1

4

Sample Output #1

5

Sample Input #2

5

Sample Output #2

6

Sample Input #3

6

Sample Output #3

11

Notes

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

见题面 Input 部分

见题面 Output 部分