나뭇잎 학회

기선이는 퀴즈를 좋아해서 알고리즘 학회에 들어가고자 하이아크에 방문하였다. 하지만 학회 문 앞에는 단 한 개의 전구, 여러 개의 스위치와 함께 다음과 같은 쪽지가 붙어있었다.

보이는 것과 같이 하나의 전구와 $N \times N$ 개의 스위치가 $N \times N$ 배열로 있습니다.
이 스위치 중 단 하나만 전구와 연결되어 있으며, 연결된 스위치를 누르면 전구가 깜빡입니다.
스위치에는 특수 장치가 적용되어 있어서 상하좌우로 인접한 두 개의 스위치를 동시에 눌러야만 합니다.
예를 들어 $N=3$ 일 때, 당신이 $5$ 번 스위치를 누르고 싶다면 인접한 스위치 상( $2$ ), 하( $8$ ), 좌( $4$ ), 우( $6$ ) 중 하나의 스위치와 같이 한 번에 눌러야 합니다.
당신은 전구와 연결된 스위치가 어느 것인지 알아내서 답을 제출해야 합니다.

'너무 쉽잖아' 생각하고 스위치를 누르려는 순간, 밑에 작게 쓰여있는 글씨를 보고 경악하고 말았다.

귀찮음이 많은 기선이는 밖에서 최소한의 나뭇잎만 주워오려고 한다. 어떤 경우에도 정답을 맞히는 데 필요한 나뭇잎의 최소 개수를 여러분이 대신 구해보자.

$N$ 이 주어진다. ( $1 \le N \le 1\\,000$ )

어떤 경우에도 정답을 맞히는 데 필요한 나뭇잎의 최소 개수를 출력한다.

$N=2$ 일 때는 다음과 같다.

ⅰ) 전구가 $1$ 번 스위치와 연결되어 있는 경우

$2$ 번, $3$ 번, $4$ 번 스위치를 눌렀으나 전구가 깜빡이지 않았으므로 $1$ 번 스위치가 전구와 연결되어 있다는 사실을 알 수 있다.

ⅱ) 전구가 $2$ 번 스위치와 연결되어 있는 경우

$2$ 번 스위치가 전구와 연결되어 있다는 사실을 알 수 있다.

ⅲ) 전구가 $3$ 번 스위치와 연결되어 있는 경우

$3$ 번 스위치가 전구와 연결되어 있다는 사실을 알 수 있다.

ⅳ) 전구가 $4$ 번 스위치와 연결되어 있는 경우

$4$ 번 스위치가 전구와 연결되어 있다는 사실을 알 수 있다.

전구가 $1$ 번, $2$ 번, $3$ 번, $4$ 번 중 어떤 스위치와 연결되어 있든 최대 2개의 나뭇잎으로 전구의 위치를 찾을 수 있으니 필요한 나뭇잎의 최소 개수는 2개이다.