Leaves at the Academy

Time limit1sMemory limit1024 MB

Summary

Given an N by N grid, find the fewest adjacent switch pairs to press so the bulb's switch is identified in every case.

Level: Medium5 of 10
Topics: Math, Implementation
Solved: No attempts yet

Problem

Kiseon likes quizzes, so he visited Hydro ACM to join an algorithm club. But at the door of the club, a single bulb and several switches were posted with a note like this:

As shown, there is one bulb and $N \times N$ switches arranged in an $N \times N$ grid.
Only one of these switches is connected to the bulb, and pressing the connected switch makes the bulb blink.
The switches have a special device: you must press two adjacent switches (up, down, left, or right) at the same time.
For example, when $N=3$ , if you want to press switch $5$ , you must press it together with one of its adjacent switches: up ( $2$ ), down ( $8$ ), left ( $4$ ), or right ( $6$ ).
You must find out which switch is connected to the bulb and submit the answer.

When Kiseon was about to press a switch, thinking 'this is too easy', he noticed small print at the bottom and was shocked.

However, each time you press two switches at once, you must submit one leaf through the gap under the door.

Kiseon hates hassle and wants to collect as few leaves as possible outside. Find the minimum number of leaves needed to answer correctly in every case.

Input

$N$ is given. ( $1 \le N \le 1\,000$ )

Output

Print the minimum number of leaves needed to answer correctly in every case.

Hint

When $N=2$ , the cases are as follows.

i) The bulb is connected to switch 1.

Press switches 3 and 4 together. The bulb does not blink.
Press switches 2 and 4 together. The bulb does not blink.

Switches 2, 3, and 4 were pressed and the bulb never blinked, so switch 1 must be the one connected to the bulb.

ii) The bulb is connected to switch 2.

Press switches 3 and 4 together. The bulb does not blink.
Press switches 2 and 4 together. The bulb blinks.

Switch 2 is known to be connected to the bulb.

iii) The bulb is connected to switch 3.

Press switches 3 and 4 together. The bulb blinks.
Press switches 2 and 4 together. The bulb does not blink.

Switch 3 is known to be connected to the bulb.

iv) The bulb is connected to switch 4.

Press switches 3 and 4 together. The bulb blinks.
Press switches 2 and 4 together. The bulb blinks.

Switch 4 is known to be connected to the bulb.

Whichever of switches 1 to 4 the bulb is connected to, its position can be found with at most 2 leaves, so the minimum number of leaves needed is 2.

Examples4

Example 1
Input
```
1
```
Expected output
```
0
```
Example 2
Input
```
2
```
Expected output
```
2
```
Example 3
Input
```
3
```
Expected output
```
5
```
Example 4
Input
```
4
```
Expected output
```
8
```