21869번 - Maximum Bishop 스페셜 저지

문제

체스에는 대각선 방향으로 움직일 수 있는 비숍(bishop)이 있다. 다음 그림과 같은 5ドル\times5$ 정사각형 체스판 위의 B라고 표시된 곳에 비숍이 있을 때, 비숍은 대각선 방향으로 움직여 X로 표시된 칸에 있는 다른 말을 잡을 수 있다.

$N$-Maximum Bishop 문제는 $N \times N$ 체스판 위에 최대한 많은 비숍을 서로 공격할 수 없도록 배치하는 문제다.

$N$이 주어졌을 때, 최대한 많은 비숍을 서로 공격할 수 없도록 배치해보자.

입력

첫째 줄에 N이 주어진다. (1ドル \leq N \leq 524,288円$)

출력

배치할 수 있는 비숍의 최대 개수 $M$을 첫 번째 줄에 출력한다. 이후 $M$개의 줄에 걸쳐 비숍을 배치해야 하는 행의 번호와 열의 번호를 공백으로 구분해서 출력한다. 행과 열의 번호는 1ドル$부터 시작한다.

답이 여러 개인 경우에는 그중 아무거나 출력한다.

제한

힌트