Dla ważonego, nieskierowanego grafu prostego $G$ z $N$ wierzchołkami (numerowanymi od $1$ do $N$) i $M$ krawędziami definiujemy wynik leśny w następujący sposób:

1. Niech $F_1, F_2, F_3, \ldots, F_M$ będą grafami składającymi się z $N$ wierzchołków (numerowanych od $1$ do $N$) i bez żadnych krawędzi.
2. Niech $e_1, e_2, \ldots, e_M$ będą krawędziami $G$ posortowanymi niemalejąco według wag. Dla $i = 1, 2, \ldots, M$ wykonujemy po kolei następujące czynności:
   • Znajdź najmniejszą dodatnią liczbę całkowitą $j$ taką, że dodanie $e_i$ do $F_j$ nie powoduje powstania cyklu, i dodaj $e_i$ do $F_j$. Dodanie $e_i$ oznacza dodanie do $F_j$ krawędzi łączącej wierzchołki $u_i$ i $v_i$ (końce $e_i$).
3. Największe $i$, dla którego $F_i$ zawiera co najmniej jedną krawędź, nazywamy wynikiem leśnym grafu $G$.

Otrzymałeś zadanie wygenerowania grafu $G$ o wyniku leśnym dokładnie $k$ i co najwyżej $2024$ wierzchołkach dla danej dodatniej liczby całkowitej $k$.

Ponieważ to zadanie było dla Ciebie zbyt łatwe, uznałeś za bardziej interesujące znalezienie grafu $G$ spełniającego następujące dodatkowe warunki:

• Jeśli liczba wierzchołków $G$ wynosi $N$, to liczba krawędzi wynosi $(2N-2)$.
• Można pokolorować $(N-1)$ krawędzi $G$ na czerwono, a pozostałe $(N-1)$ krawędzi na niebiesko, tak aby same czerwone krawędzie tworzyły drzewo i same niebieskie krawędzie również tworzyły drzewo.

Mając dane $k$, znajdź i wypisz graf $G$ spełniający te warunki.

Wejście

Pierwszy wiersz zawiera liczbę całkowitą $k$. ($2 \le k \le 12$)

Wyjście

Pierwszy wiersz powinien zawierać liczbę wierzchołków $N$ grafu $G$. ($2 \le N \le 2024$)

Następnie w $(2N-2)$ wierszach wypisz po trzy liczby całkowite $a_i$, $b_i$, $c_i$ oddzielone spacjami. ($1 \le a_i, b_i \le N$; $a_i \neq b_i$; $1 \le c_i \le 10^9$) Oznacza to krawędź o wadze $c_i$ łączącą wierzchołki $a_i$ i $b_i$.

Graf $G$ musi spełniać następujące warunki:

• Wszystkie wagi krawędzi są różne, czyli wszystkie $c_i$ są parami różne.
• Pierwszych $N-1$ wypisanych krawędzi tworzy drzewo. Podobnie kolejne $N-1$ krawędzi również tworzy drzewo.
• Żadna para wierzchołków nie jest połączona bezpośrednio więcej niż jedną krawędzią.
• Wynik leśny grafu $G$ wynosi $k$.

Przykład

Wejście 1

3

Wyjście 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

Uwagi

Poniżej znajduje się przykład poprawnej odpowiedzi dla $k=3$.

Powyższy graf składa się z dwóch rozłącznych drzew, co widać na poniższym rysunku.

Wynik leśny wynosi $3$, jak pokazano poniżej. Czerwone krawędzie należą do $F_1$, niebieskie do $F_2$, a zielone do $F_3$.