"Astra" is a beautiful boardgame where players take turns discovering constellations by marking the stars. This game is a clever mix of tactics and strategy, with a streamlined and intuitive rule set that makes it easy to pick up and quick to play.

Photo by @kavics004 on BoardGameGeek

Consider a two-player game between Alice and Bob. In this game, there is a tree-shaped constellation, which can be regarded as a connected graph consisting of $n$ stars (numbered from $1$ to $n$) and $(n - 1)$ edges. At the beginning, only one star $s$ is marked. Alice and Bob take turns marking the remaining stars according to the following rule:

• Each turn, a player should mark at least $1$ star and at most $k$ stars.
• Each star can be marked only once.
• Let $a_1, a_2, \cdots, a_p$ be the stars marked in a turn, in the order they are marked:
  • When marking $a_1$, it must be a neighbor of a marked star.
  • For all $2 \le i \le p$, when marking $a_i$, it must be a neighbor of $a_{i-1}$.

Two stars $u$ and $v$ are neighbors if they are directly connected by an edge.

The player who marks the last star wins the constellation. Given that Alice is the first to play and both players play optimally, for each $1 \le s \le n$, determine who will win the constellation.

Input

There are multiple test cases. The first line of the input contains an integer $T$ ($1 \le T \le 100$), indicating the number of test cases. For each test case:

The first line contains two integers $n$ and $k$ ($2 \le n \le 2 \times 10^3$, $1 \le k < n$), indicating the number of stars and the maximum number of stars marked in each turn.

For the following $(n - 1)$ lines, the $i$-th line contains two integers $u_i$ and $v_i$ ($1 \le u_i, v_i \le n$), indicating that there is an edge connecting stars $u_i$ and $v_i$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \times 10^3$.

Output

For each test case, output one line containing a string $d_1 d_2 \cdots d_n$ ($d_i \in \{0, 1\}$), where $d_i$ indicates who will win the constellation when $s = i$. If Alice will win, then $d_i = 1$; otherwise, if Bob will win, then $d_i = 0$.

Example

Input 1

3
6 2
1 2
3 2
3 4
5 3
2 6
3 1
1 2
2 3
3 2
1 2
2 3

Output 1

011000
000
101

Note

The first sample test case is illustrated above.

• Consider $s = 1$. For the first turn, Alice has three choices: mark $\{2\}$, $\{2, 3\}$, or $\{2, 6\}$. If Alice chooses $\{2, 6\}$, Bob can then mark $\{3\}$, and $2$ separated stars will remain. For the following turns, each player can only mark one star, and Bob will be the winner. Alice's other choices can be analyzed likewise.
• Consider $s = 2$. For the first turn, Alice has five choices: mark $\{1\}$, $\{3\}$, $\{6\}$, $\{3, 4\}$, or $\{3, 5\}$. Alice can choose to mark $\{3\}$, and $4$ separated stars will remain. For the following turns, each player can only mark one star, and Alice will be the winner.

For the second sample test case, as $k = 1$, there will be exactly $3 - 1 = 2$ turns, so Bob will always be the winner.

For the third sample test case, if $s = 1$ or $s = 3$, Alice can directly mark the remaining $2$ stars and win the constellation.