二部グラフが与えられる。このグラフの左右にはそれぞれ $n$ 個の頂点がある。グラフの各辺には色がついており、色は $1$ から $k$ までの整数で表される。

任意の色の部分集合 $S \subseteq \{1, 2, \dots, k\}$ について、ある完全マッチングが存在し、そのマッチングで使用される辺の色がちょうど $S$ であるとき、その集合を「良い」と呼ぶ。具体的には、求める完全マッチングは以下の2つの条件を満たす必要がある。

1. マッチングに含まれるすべての辺の色は $S$ に含まれる。
2. $S$ に含まれる任意の色の $c$ について、マッチングの中にその色が $c$ である辺が少なくとも1つ存在する。

今、あなたは高々1本の辺の色を、その辺の元の色の隣接色に変更することができる。各色の部分集合について、変更後にその色の部分集合が「良い」状態になるような変更方法が存在するかどうかを判定したい。色 $x$ と色 $y$ が隣接するとは、$|x - y| = 1$ または $|x - y| = k - 1$ であることと定義する。

各色の部分集合 $S$ に対して、判定結果を出力せよ。

入力

各テストファイルには複数のテストケースが含まれる。最初の行にテストケースの数 $T$ ($1 \le T \le 50$) が与えられる。各テストケースの形式は以下の通りである。

1行目に3つの整数 $n, m, k$ ($1 \le n \le 50, 1 \le m \le n^2, 1 \le k \le 10$) が与えられ、それぞれ二部グラフの頂点数、辺数、色の数を表す。

続く $m$ 行には、それぞれ3つの整数 $u, v, c$ ($1 \le u, v \le n, 1 \le c \le k$) が与えられ、左側の $u$ 番目の頂点と右側の $v$ 番目の頂点を結ぶ色 $c$ の辺が存在することを表す。グラフに多重辺は存在しないことが保証される。

各テストファイルにおいて、すべてのテストケースの $2^k$ の総和は $2048$ を超えないことが保証される。

出力

各テストケースについて、$2^k$ 個の文字からなる1行を出力せよ。$i$ 番目の文字は、以下の色の集合 $S$ に対する答えを表す：$j \in [1, k]$ について、$i - 1$ の二進数表現における下位から $j$ ビット目が $1$ であれば $j \in S$ であり、そうでなければ $j \notin S$ である。この集合 $S$ に対して、高々1本の辺の色をその隣接色に変更した後に条件を満たす完全マッチングが存在する場合は "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