Для взвешенного неориентированного простого графа $G$ с $N$ вершинами (от $1$ до $N$) и $M$ рёбрами оценка леса определяется следующим образом:

1. Пусть $F_1$, $F_2$, $F_3$, $\ldots$, $F_M$ — графы, каждый из которых содержит $N$ вершин (от $1$ до $N$) и не имеет рёбер.
2. Пусть рёбра графа $G$ упорядочены по возрастанию веса: $e_1$, $e_2$, $\ldots$, $e_M$. Для $i=1, 2, \ldots, M$ последовательно выполняем следующее:
   • Найдём наименьшее положительное целое $j$, такое что добавление $e_i$ в $F_j$ не создаёт цикла, и добавим $e_i$ в $F_j$. Здесь добавление $e_i$ означает, что если концы $e_i$ имеют номера $u_i$ и $v_i$, то в $F_j$ добавляется ребро, соединяющее вершину $u_i$ с вершиной $v_i$.
3. Наибольшее $i$, для которого $F_i$ содержит хотя бы одно ребро, называется оценкой леса графа $G$.

Вам поручено построить граф $G$ с не более чем $2024$ вершинами, оценка леса которого в точности равна заданному положительному целому $k$.

Поскольку эта задача показалась вам слишком лёгкой, вы решили, что интереснее найти граф $G$, удовлетворяющий следующим дополнительным условиям:

• Если количество вершин графа $G$ равно $N$, то количество рёбер равно $(2N-2)$.
• Среди рёбер $G$ можно покрасить $(N-1)$ ребро в красный цвет, а другие $(N-1)$ — в синий, так что если оставить только красные рёбра, получится дерево, и если оставить только синие, тоже получится дерево.

По заданному $k$ найдите и выведите граф $G$, удовлетворяющий этим условиям.

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

В первой строке задано целое число $k$. ($2 \le k \le 12$)

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

В первой строке выведите количество вершин $N$ графа $G$. ($2 \le N \le 2024$)

В следующих $(2N-2)$ строках выведите три целых числа $a_i$, $b_i$, $c_i$, разделённых пробелами. ($1 \le a_i, b_i \le N$; $a_i \neq b_i$; $1 \le c_i \le 10^9$) Это означает, что существует ребро веса $c_i$, соединяющее вершины $a_i$ и $b_i$.

Граф $G$ должен удовлетворять следующим условиям:

• Веса всех рёбер различны. То есть все $c_i$ различны.
• Первые $N-1$ выведенных рёбер образуют дерево. Аналогично, следующие $N-1$ рёбер также образуют дерево.
• Не существует пары вершин, соединённых двумя или более рёбрами напрямую.
• Оценка леса графа $G$ равна $k$.

Примеры

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

3

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

5
1 2 8
2 3 1
3 4 2
4 5 5
1 3 6
3 5 4
5 2 7
2 4 3

Примечание

Ниже приведён пример правильного ответа для $k=3$.

Как видно на следующем рисунке, этот граф состоит из двух непересекающихся деревьев.

Вычисление оценки леса даёт $3$, как показано ниже. Красные рёбра принадлежат $F_1$, синие — $F_2$, зелёные — $F_3$.