Una matrice buona di dimensione $N$ è una matrice $N \times N$ di interi positivi tale che lo XOR totale di ogni riga, di ogni colonna e di entrambe le diagonali sia $0$.

Più precisamente, una matrice $N \times N$ $A$ è chiamata una matrice buona di dimensione $N$ se soddisfa tutte le seguenti condizioni. Qui, $x \oplus y$ indica lo XOR bit a bit di $x$ e $y$, e $\bigoplus_{i=1}^N a_i = a_1 \oplus \dots \oplus a_N$.

• $A_{i,j}$ ($1 \le i, j \le N$) è un intero positivo.
• Per ogni $i = 1, 2, \dots, N$, $\bigoplus_{j=1}^N A_{i,j} = 0$.
• Per ogni $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$.

Viene dato un intero positivo $N$.

Tra tutte le matrici buone di dimensione $N$, stampane una la cui somma totale di tutti gli elementi, $\sum_{1 \le i, j \le N} A_{i,j}$, sia minima.

Se non esiste alcuna matrice buona di dimensione $N$, segnalalo.

Input

L'input consiste in un singolo intero $N$. ($1 \le N \le 2 \times 10^3$)

Output

Se non esiste alcuna matrice buona di dimensione $N$, stampa $-1$ su una singola riga.

Se esiste, stampa sulla prima riga la minima somma totale possibile di tutti gli elementi.

Quindi stampa la matrice $A$ nelle successive $N$ righe, con gli elementi separati da spazi. Cioè, la $(i+1)$-esima riga deve contenere gli elementi della $i$-esima riga della matrice $A$, separati da spazi.

Se esistono più soluzioni, è possibile stamparne una qualsiasi.

Esempi

Input di esempio 1

2

Output di esempio 1

4
1 1
1 1

Input di esempio 2

1

Output di esempio 2

-1

Note

Per il primo esempio, lo XOR totale di ogni riga, di ogni colonna e di entrambe le diagonali è $0$, quindi soddisfa le condizioni per una matrice buona. Inoltre, tra tutte le matrici buone di dimensione $2$, la somma totale di tutti gli elementi non può essere resa inferiore a $4$, quindi il valore minimo è $4$.

Per il secondo esempio, non esiste alcuna matrice buona di dimensione $1$, quindi stampa $-1$.

Lo XOR bit a bit $x \oplus y$ di interi non negativi $x, y$ è definito come segue.

• Nella rappresentazione binaria di $x \oplus y$, la cifra nella posizione $2^k$ ($k \ge 0$) è $1$ se e solo se esattamente una delle cifre nella posizione $2^k$ nelle rappresentazioni binarie di $x$ e $y$ è $1$; altrimenti è $0$.

Ad esempio, $3 \oplus 5 = 6$ (in binario, $011 \oplus 101 = 110$).