Well-Read

Time limit2sMemory limit512 MB

Summary

Given n students who each hold a different book, output at most 4950 pairwise swaps so that every student eventually holds every book.

Level: Medium6 of 10
Topics: Implementation, Recursion
Solved: No attempts yet

Problem

There are $n$ students at FER, numbered 1, 2, ..., $n$ . They decide to read $n$ classic works of world literature. Each student buys one book, and all the books are different. Then they read every purchased book by exchanging books with each other.

At every moment, each student holds exactly one of the $n$ books. At the start, each student holds the book they bought. When two students finish the books they currently hold, they can swap books.

Organize the swaps so that every student eventually obtains every book. The total number of swaps must be at most 4950.

Input

A single natural number $n$ , the number of students. It satisfies $2 \le n \le 100$ .

Output

Print at most 4950 swaps, one per line, in the order they happen. Write each swap as two integers separated by a space, the numbers of the two students who exchange books.

Examples1

Example 1
Input
```
3
```
Expected output
```
1 2
1 3
1 3
2 3
```