Phone Company#13012

Phone Company

2 seconds
512 megabytes
Medium

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:

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:

Input

The input consists of a single integer .

1 \le k \le 1000.

Output

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.

Examples

Example

Loading
Loading

Note

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.