Il nano Esteta è un noto intenditore d'arte. Nella sua casa possiede una vasta collezione di dipinti. Il suo dipinto preferito raffigura un grafo su 10 vertici che appare come segue:

Un'illustrazione dell'output nel primo esempio.

Un giorno, ammirando il suo dipinto preferito, il nano ha capito quali proprietà rendono questo grafo così straordinario: è connesso, ogni vertice ha esattamente 3 archi incidenti e il grafo non contiene cicli di lunghezza 4 (cioè non esistono quattro archi $(v_1, v_2)$, $(v_2, v_3)$, $(v_3, v_4)$ e $(v_4, v_1)$ per alcun insieme di quattro vertici distinti $v_1, v_2, v_3, v_4$).

Folgorato da questa scoperta, il nano Esteta si è chiesto se esistano altri grafi con queste proprietà. Poiché vuole diventare un pezzo grosso nel mondo dell'arte, è interessato solo ai grafi grandi, vale a dire quelli con almeno 42 vertici (per qualche motivo 42 gli sembra proprio un bel numero).

Aiuta il nano: per un dato numero di vertici, produci un grafo semplice non orientato (senza cappi né archi multipli tra la stessa coppia di vertici) con queste proprietà, oppure determina che un tale grafo non esiste.

Input

La prima e unica riga di input contiene un singolo intero $N$, il numero di vertici.

Output

Se non esiste alcuna soluzione, stampa NO.

Altrimenti, nella prima riga, stampa un singolo intero $M$, il numero di archi nel grafo.

Ciascuna delle successive $M$ righe deve contenere due interi $a_i$ e $b_i$ ($1 \le a_i, b_i \le N$), che rappresentano gli estremi di un arco.

Se esistono più soluzioni valide, puoi stamparne una qualsiasi.

Vincoli

$42 \le N \le 10^6$.

Esempi

Input 1

10

Output 1

15
1 2
2 3
3 4
4 5
5 1
1 6
2 7
3 8
4 9
5 10
6 8
8 10
10 7
7 9
9 6

Input 2

8

Output 2

NO

Note

Attenzione: gli esempi sopra riportati non soddisfano la condizione $N \ge 42$, quindi non è richiesto che il tuo programma li superi. Il caso di esempio nel sistema di valutazione ha $N = 42$.