給定一個二分圖，其中左右兩側各包含 $n$ 個頂點。圖中每條邊均有一個顏色，顏色可以用一個整數表示，範圍在 $1$ 到 $k$ 之間。

對於任意顏色子集 $S \subseteq \{1, 2, \dots, k\}$，我們稱它為「好的」，當且僅當存在一組完美匹配，使得該匹配使用的邊的顏色恰好為 $S$。具體來說，所尋找的完美匹配需要滿足以下兩個條件：

1. 匹配中的所有邊顏色均來自 $S$；
2. 對於 $S$ 中的任一顏色 $c$，匹配中至少存在一條邊的顏色為 $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]$，如果 $i - 1$ 的二進位表示中從低到高第 $j$ 位為 $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

輸出 1

0101
00010111