Given a bipartite graph where each of the left and right sides contains $n$ vertices. Each edge in the graph has a color, which can be represented by an integer in the range $[1, k]$.

For any subset of colors $S \subseteq \{1, 2, \dots, k\}$, we call it "good" if and only if there exists a perfect matching such that the set of colors of the edges used in the matching is exactly $S$. Specifically, the perfect matching must satisfy the following two conditions: 1. All edges in the matching have colors from $S$; 2. For every color $c \in S$, there is at least one edge in the matching with color $c$.

Now, you can change the color of at most one edge to an adjacent color of its original color. For each subset of colors, you want to know if there exists a modification scheme such that the subset becomes good after the modification. Two colors $x$ and $y$ are adjacent if and only if $|x - y| = 1$ or $|x - y| = k - 1$.

For each subset of colors $S$, output the corresponding result.

Input

Each test file contains multiple test cases. The first line contains the number of test cases $T$ ($1 \le T \le 50$). The format for each test case is as follows:

The first line contains three integers $n, m, k$ ($1 \le n \le 50, 1 \le m \le n^2, 1 \le k \le 10$), representing the number of vertices on each side of the bipartite graph, the number of edges, and the number of colors, respectively.

The next $m$ lines each contain three integers $u, v, c$ ($1 \le u, v \le n, 1 \le c \le k$), representing an edge connecting the $u$-th vertex on the left side and the $v$-th vertex on the right side with color $c$. It is guaranteed that there are no multiple edges between the same pair of vertices.

Within each test file, the sum of $2^k$ over all test cases does not exceed $2048$.

Output

For each test case, output a single line containing $2^k$ characters. The $i$-th character represents the answer for the color subset $S$ defined as follows: for $j \in [1, k]$, if the $j$-th bit (from least significant to most significant) of $i - 1$ is $1$, then $j \in S$, otherwise $j \notin S$. For this set $S$, if there exists a valid perfect matching after changing at most one edge to an adjacent color, output "1", otherwise output "0".

Examples

Input 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

Output 1

0101
00010111