A mobile phone company offers the following promotion: each new customer may choose exactly other phone numbers and all calls between the customer and any of the chosen contacts are free (in both directions).
A group of students (numbered from 1 to ) wants to take advantage of this promotion. Each student must choose exactly distinct contacts from the set \{1,2,\dots,n\} \setminus \{i\}.
We say that two students and can talk for free if at least one of the following holds:
has chosen as one of the free contacts, or
has chosen 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 with 1 \le i < j \le n, students and can talk for free.
For a given , your task is to:
determine the maximum possible number of students for which such a configuration is possible,
construct one valid configuration of chosen contacts for this maximum .
The input consists of a single integer .
1 \le k \le 1000.
On the first line, output a single integer – 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 lines, output the free contacts chosen by each student: on line i+1 (for 1 \le i \le n), output 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 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.
Example
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.