write a go solution for Description:
You are given a board with n rows and n columns, numbered from 1 to n. The intersection of the a-th row and b-th column is denoted by (a,b).

A half-queen attacks cells in the same row, same column, and on one diagonal. More formally, a half-queen on (a,b) attacks the cell (c,d) if a=c or b=d or a-b=c-d.

The blue cells are under attack.

Construct an optimal solution.

Input Format:
The first line contains a single integer n (1<=n<=10^5) — the size of the board.

Output Format:
In the first line print a single integer k — the minimum number of half-queens.

In each of the next k lines print two integers a_i, b_i (1<=a_i,b_i<=n) — the position of the i-th half-queen.

If there are multiple solutions, print any.

Note:
Example 1: one half-queen is enough. Note: a half-queen on (1,1) attacks (1,1).

Example 2: one half-queen is enough too. (1,2) or (2,1) would be wrong solutions, because a half-queen on (1,2) does not attack the cell (2,1) and vice versa. (2,2) is also a valid solution.

Example 3: it is impossible to cover the board with one half queen. There are multiple solutions for 2 half-queens; you can print any of them.. Output only the code with no comments, explanation, or additional text.