Covering Newspaper Answers

Given an \(N \times N\) grid representing an English newspaper, certain cells contain an answer. For a cell \((x, y)\), an answer is present if and only if \(\gcd(x, y) > 1\). As a token of gratitude for making a PPT, XHY sends CYD a copy of the newspaper answers. XHY’s phone can photograph a \(1 \times 2\) subgrid (which may be placed horizontally or vertically). A photograph, or domino, covers exactly two adjacent cells.

The task is to select a set of photographs so that every cell that contains an answer is covered by at least one photograph. If two answer cells are adjacent (and hence can be covered by one domino), they save one photograph compared to covering them individually (since a domino must always cover two cells, even if one is not an answer).

This can be formulated as follows: Let \(S\) be the set of cells where \(\gcd(x,y)>1\). Find the minimum number of domino placements (each covering two adjacent cells) such that every cell in \(S\) is contained in at least one domino. It is optimal to pair adjacent answer cells if possible; otherwise, an isolated answer cell must be covered by a domino placed over it and any adjacent cell.

inputFormat

The input consists of a single integer \(N\) \((1 \leq N \leq 1000)\) indicating the dimensions of the grid.

outputFormat

Output a single integer — the minimum number of photographs required to cover all answer cells.

sample

1

0