Используя только резисторы с сопротивлением $1$ [Ом], сконструируйте резистор с сопротивлением $\sqrt{D}$ [Ом].

Вам дано целое положительное число $D$. Сконструируйте связный неориентированный граф, удовлетворяющий всем следующим условиям. В рамках ограничений данной задачи можно доказать, что такой граф всегда существует.

• Количество вершин $N$ находится в диапазоне от $2$ до $300$ включительно, и каждая вершина имеет уникальный номер от $1$ до $N$.
• Количество ребер $M$ не превышает $300$; допускаются петли и кратные ребра.
• «Эффективное сопротивление между вершиной $1$ и вершиной $N$», определенное ниже, должно отличаться от $\sqrt{D}$ не более чем на $10^{-6}$ по абсолютной величине.

Пусть $G$ — связный неориентированный граф с $n$ вершинами и $m$ ребрами ($n \ge 2$), и пусть $j$-е ребро соединяет вершины $a_j, b_j$. Рассмотрим присвоение вещественного числа $V_i$ ($i = 1, 2, \dots, n$) каждой вершине графа $G$ и вещественного числа $I_j$ ($j = 1, 2, \dots, m$) каждому ребру так, чтобы выполнялись все следующие уравнения:

• $I_j = V_{a_j} - V_{b_j}$ ($j = 1, 2, \dots, m$)
• $\sum_{b_j=i} I_j - \sum_{a_j=i} I_j = 0$ ($i = 2, 3, \dots, n - 1$)
• $\sum_{b_j=n} I_j - \sum_{a_j=n} I_j = 1$

Можно доказать, что такое присвоение всегда существует, и, более того, значение $V_1 - V_n$ определено однозначно. Мы называем это значение «эффективным сопротивлением между вершиной $1$ и вершиной $n$».

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

Входные данные состоят из одного целого положительного числа $D$ ($1 \le D \le 5000$).

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

В первой строке выведите количество вершин $N$ и количество ребер $M$ сконструированного графа в указанном порядке, разделенные пробелами.

В каждой из следующих $M$ строк выведите концы $i$-го выбранного ребра ($i = 1, 2, \dots, M$), разделенные пробелом.

Если существует несколько графов, удовлетворяющих условиям, можно вывести любой из них.

Примеры

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

1

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

4 5
1 2
1 3
2 3
2 4
3 4

Примечание

Ниже приведена иллюстрация вывода для первого примера.

То, что эффективное сопротивление между вершиной $1$ и вершиной $n$ равно $1$ [Ом], можно объяснить следующим образом:

• Поскольку все резисторы имеют сопротивление $1$ [Ом], а потенциалы в вершинах $2$ и $3$ равны в силу симметрии, резистор между ними можно считать отсутствующим.
• В результате цепь сводится к двум параллельным ветвям, каждая из которых состоит из двух последовательно соединенных резисторов по $1$ [Ом].
• Эффективное сопротивление двух последовательно соединенных резисторов по $1$ [Ом] равно $2$ [Ом], а эффективное сопротивление двух параллельно соединенных резисторов по $2$ [Ом] равно $1$ [Ом].

Следующий вывод также считается верным:

2 1
1 2