P4905 Newspaper

After finally making it through three years of middle school, the “Learn English Newspaper” still lingers. When the first issue of the Grade 10 “Learn English Newspaper” floated onto his desk, CYD dashen felt despair; however, there was still a glimmer of hope—classmate XHY always finishes faster.

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.

One line, a positive integer $N$.

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

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