При подготовке данных для задачи D: ㄷㄷㄷㅈ, составители UCPC обнаружили, что создавать DUDUDUNGA-деревья с большим количеством вершин довольно сложно. Давайте напишем программу, которая для заданного $N$ выводит DUDUDUNGA-дерево с $N$ вершинами.

Входные данные

В первой строке задано количество вершин дерева $N$ ($6 \le N \le 300\,000$).

Выходные данные

Выведите $N-1$ строку, каждая из которых содержит два конца ребра, разделенных пробелом. Номера вершин должны быть целыми числами от $1$ до $N$.

Примеры

Входные данные 1

6

Выходные данные 1

1 2
2 3
3 4
4 5
4 6

Примечание

Определение DUDUDUNGA-дерева можно найти в задаче D: ㄷㄷㄷㅈ. Для любого заданного $N$ всегда существует DUDUDUNGA-дерево с $N$ вершинами.