Phone Company

Limits: 2 sec., 512 MiB

A mobile phone company offers the following promotion: each new customer may choose exactly \(k\) other phone numbers and all calls between the customer and any of the \(k\) chosen contacts are free (in both directions).

A group of \(n\) students (numbered from 1 to \(n\)) wants to take advantage of this promotion. Each student \(i\) must choose exactly \(k\) distinct contacts from the set \(\{1,2,\dots,n\} \setminus \{i\}\).

We say that two students \(i\) and \(j\) can talk for free if at least one of the following holds:

• \(i\) has chosen \(j\) as one of the free contacts, or

• \(j\) has chosen \(i\) as one of the free contacts.

The students want to choose their free contacts so that any student can talk to any other student for free, i.e., for every pair \((i, j)\) with \(1 \le i < j \le n\), students \(i\) and \(j\) can talk for free.

For a given \(k\), your task is to:

• determine the maximum possible number \(n\) of students for which such a configuration is possible,

• construct one valid configuration of chosen contacts for this maximum \(n\).

Input

The input consists of a single integer \(k\).

Output

On the first line, output a single integer \(n\) – the maximum number of students for which it is possible to choose the free contacts so that any two students can talk to each other for free.

On the next \(n\) lines, output the \(k\) free contacts chosen by each student: on line \(i+1\) (for \(1 \le i \le n\)), output \(k\) distinct integers \(a_{i,1}, a_{i,2}, \dots, a_{i,k}\). Each \(a_{i,j}\) must satisfy \(1 \le a_{i,j} \le n\) and \(a_{i,j} \ne i\). These lines indicate that student \(i\) has chosen the students \(a_{i,1}, a_{i,2}, \dots, a_{i,k}\) as their free contacts.

If there are several valid answers, print any of them.

Constraints

\(1 \le k \le 1000\).

Samples

Input (stdin) сopy	Output (stdout) сopy
2	5 2 5 3 4 1 5 1 3 2 4

Notes

In the example, \(k = 2\) and the maximum number of students for which it is possible to choose the free contacts so that any two students can talk to each other for free is \(n = 5\). For each pair of distinct students, at least one of them has chosen the other, so any two can talk for free.