Dany jest graf dwudzielny, w którym każda ze stron zawiera $n$ wierzchołków. Każda krawędź w grafie ma przypisany kolor, który można wyrazić jako liczbę całkowitą z zakresu od $1$ do $k$.

Dla dowolnego podzbioru kolorów $S \subseteq \{1, 2, \dots, k\}$ nazywamy go dobrym wtedy i tylko wtedy, gdy istnieje takie skojarzenie doskonałe, że zbiór kolorów krawędzi użytych w tym skojarzeniu jest dokładnie równy $S$. Mówiąc dokładniej, poszukiwane skojarzenie doskonałe musi spełniać dwa warunki: 1. Wszystkie krawędzie w skojarzeniu mają kolory należące do $S$. 2. Dla każdego koloru $c \in S$ w skojarzeniu istnieje co najmniej jedna krawędź o kolorze $c$.

Możesz zmienić kolor co najwyżej jednej krawędzi na kolor sąsiedni względem jej oryginalnego koloru. Dla każdego podzbioru kolorów chcesz sprawdzić, czy istnieje sposób modyfikacji, po którym ten podzbiór kolorów stanie się dobry. Kolory $x$ oraz $y$ są sąsiednie wtedy i tylko wtedy, gdy $|x - y| = 1$ lub $|x - y| = k - 1$.

Dla każdego podzbioru kolorów $S$ wypisz wynik sprawdzenia.

Wejście

Każdy plik testowy zawiera wiele zestawów danych. Pierwsza linia zawiera liczbę zestawów danych $T$ ($1 \le T \le 50$). Format każdego zestawu danych jest następujący:

Pierwsza linia zawiera trzy liczby całkowite $n, m, k$ ($1 \le n \le 50, 1 \le m \le n^2, 1 \le k \le 10$), oznaczające odpowiednio liczbę wierzchołków po każdej stronie grafu dwudzielnego, liczbę krawędzi oraz liczbę kolorów.

Następnie $m$ linii, z których każda zawiera trzy liczby całkowite $u, v, c$ ($1 \le u, v \le n, 1 \le c \le k$), oznaczające krawędź łączącą $u$-ty wierzchołek lewej strony z $v$-tym wierzchołkiem prawej strony, o kolorze $c$. Gwarantuje się, że w grafie nie ma krawędzi wielokrotnych.

W każdym pliku testowym suma $2^k$ dla wszystkich zestawów danych nie przekracza $2048$.

Wyjście

Dla każdego zestawu danych wypisz w jednej linii ciąg $2^k$ znaków. $i$-ty znak reprezentuje odpowiedź dla zbioru kolorów $S$ zdefiniowanego następująco: dla każdego $j \in [1, k]$, jeśli $j$-ty bit (licząc od najmniej znaczącego) w zapisie binarnym liczby $i-1$ jest równy $1$, to $j \in S$, w przeciwnym razie $j \notin S$. Jeśli dla danego zbioru $S$ istnieje sposób modyfikacji koloru co najwyżej jednej krawędzi na kolor sąsiedni, po którym istnieje poprawne skojarzenie doskonałe, wypisz „1”, w przeciwnym razie wypisz „0”.

Przykład

Wejście 1

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

Wyjście 1

0101
00010111