Дан двудольный граф, в котором каждая из двух долей содержит $n$ вершин. Каждое ребро графа имеет цвет, который можно представить целым числом в диапазоне от $1$ до $k$.

Для любого подмножества цветов $S \subseteq \{1, 2, \dots, k\}$ мы называем его «хорошим», если и только если существует совершенное паросочетание, такое что множество цветов использованных в нем ребер в точности равно $S$. Конкретнее, искомое совершенное паросочетание должно удовлетворять следующим двум условиям: 1. Все ребра в паросочетании имеют цвета из $S$; 2. Для любого цвета $c \in S$ в паросочетании существует хотя бы одно ребро цвета $c$.

Вы можете изменить цвет не более чем одного ребра на соседний с ним цвет. Для каждого подмножества цветов необходимо определить, существует ли такой вариант изменения, при котором после него данное подмножество цветов станет «хорошим». Цвета $x$ и $y$ называются соседними, если и только если $|x - y| = 1$ или $|x - y| = k - 1$.

Для каждого подмножества цветов $S$ выведите соответствующий результат.

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

Каждый файл теста содержит несколько наборов входных данных. Первая строка содержит количество наборов данных $T$ ($1 \le T \le 50$). Формат каждого набора данных следующий:

Первая строка содержит три целых числа $n, m, k$ ($1 \le n \le 50, 1 \le m \le n^2, 1 \le k \le 10$), представляющие количество вершин в каждой доле, количество ребер и количество цветов соответственно.

Далее следуют $m$ строк, каждая из которых содержит три целых числа $u, v, c$ ($1 \le u, v \le n, 1 \le c \le k$), означающих наличие ребра между $u$-й вершиной левой доли и $v$-й вершиной правой доли, имеющего цвет $c$. Гарантируется отсутствие кратных ребер.

В каждом файле теста сумма $2^k$ по всем наборам данных не превышает $2048$.

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

Для каждого набора данных выведите строку из $2^k$ символов. $i$-й символ представляет ответ для подмножества цветов $S$, определяемого следующим образом: для $j \in [1, k]$, если $j$-й бит (считая от младшего к старшему) в двоичном представлении числа $i-1$ равен $1$, то $j \in S$, иначе $j \notin S$. Если для данного множества $S$ существует допустимое совершенное паросочетание после изменения цвета не более чем одного ребра на соседний, выведите «1», в противном случае выведите «0».

Примеры

Пример 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

Пример 2

0101
00010111