A good matrix of size $N$ is an $N \times N$ matrix of positive integers such that the total XOR of each row, each column, and both diagonals is $0$.

More precisely, an $N \times N$ matrix $A$ is called a good matrix of size $N$ if it satisfies all of the following conditions. Here, $x \oplus y$ denotes the bitwise XOR of $x$ and $y$, and $\bigoplus_{i=1}^N a_i = a_1 \oplus \dots \oplus a_N$.

• $A_{i,j}$ ($1 \le i, j \le N$) is a positive integer.
• For each $i = 1, 2, \dots, N$, $\bigoplus_{j=1}^N A_{i,j} = 0$.
• For each $j = 1, 2, \dots, N$, $\bigoplus_{i=1}^N A_{i,j} = 0$.
• $\bigoplus_{i=1}^N A_{i,i} = 0$.
• $\bigoplus_{i=1}^N A_{i,N-i+1} = 0$.

A positive integer $N$ is given.

Among all good matrices of size $N$, output one whose total sum of all elements, $\sum_{1 \le i, j \le N} A_{i,j}$, is minimum.

If no good matrix of size $N$ exists, report that.

Input

The input consists of a single integer $N$. ($1 \le N \le 2 \times 10^3$)

Output

If no good matrix of size $N$ exists, print $-1$ on a single line.

If it exists, print the minimum possible total sum of all elements on the first line.

Then print the matrix $A$ in the following $N$ lines, with elements separated by spaces. That is, the $(i+1)$-th line should contain the elements of the $i$-th row of matrix $A$, separated by spaces.

If there are multiple solutions, any of them may be printed.

Examples

Sample Input 1

2

Sample Output 1

4
1 1
1 1

Sample Input 2

1

Sample Output 2

-1

Note

For the first example, the total XOR of each row, each column, and both diagonals is $0$, so it satisfies the conditions for a good matrix. Also, among all good matrices of size $2$, the total sum of all elements cannot be made smaller than $4$, so the minimum value is $4$.

For the second example, there is no good matrix of size $1$, so print $-1$.

The bitwise XOR $x \oplus y$ of non-negative integers $x, y$ is defined as follows.

• In the binary representation of $x \oplus y$, the digit at the $2^k$ ($k \ge 0$) place is $1$ if and only if exactly one of the digits at the $2^k$ place in the binary representations of $x$ and $y$ is $1$; otherwise, it is $0$.

For example, $3 \oplus 5 = 6$ (in binary, $011 \oplus 101 = 110$).