Minimum Flowers in a Grid Town

Given an \(N \times N\) grid representing a town layout, your task is to determine the minimum number of towns that must be planted with flowers so that every \(3 \times 3\) subgrid contains at least one town with flowers. Note that the flowers can only be planted on the inner grid (i.e. excluding the boundary rows and columns), which effectively makes the plantable area an \((N-2) \times (N-2)\) grid. When \(N < 5\), the grid is small enough that a single flower is enough.

The key observation is that by partitioning the inner grid into non-overlapping \(3\times3\) subgrids (or using ceiling division when they do not perfectly fit), we can calculate the minimum number of flowers required.

Formula: If \(N \ge 5\), let \(\text{inner t{_}side} = N - 2\), then the number of flowers required is:

[ \left\lceil \frac{N-2}{3} \right\rceil \times \left\lceil \frac{N-2}{3} \right\rceil ]

Otherwise, if \(N < 5\), the answer is 1.

inputFormat

The input consists of a single integer \(N\) (\(1 \leq N \leq 10^9\)), which represents the side length of the grid.

outputFormat

Output a single integer representing the minimum number of flowers required. The output should be printed to standard output.

## sample

3

1

</p>