«Astra» è uno splendido gioco da tavolo in cui i giocatori scoprono a turno le costellazioni segnando le stelle. Questo gioco è un intelligente mix di tattica e strategia, con un regolamento snello e intuitivo che lo rende facile da imparare e veloce da giocare.

Photo by @kavics004 on BoardGameGeek

Consideriamo un gioco a due giocatori tra Alice e Bob. In questo gioco c'è una costellazione a forma di albero, che può essere vista come un grafo connesso composto da $n$ stelle (numerate da $1$ a $n$) e $(n - 1)$ archi. All'inizio, solo una stella $s$ è segnata. Alice e Bob segnano a turno le stelle rimanenti secondo la seguente regola:

• A ogni turno, un giocatore deve segnare almeno $1$ stella e al massimo $k$ stelle.
• Ogni stella può essere segnata una sola volta.
• Siano $a_1, a_2, \cdots, a_p$ le stelle segnate in un turno, nell'ordine in cui vengono segnate:
  • Quando si segna $a_1$, essa deve essere vicina a una stella già segnata.
  • Per tutti i $2 \le i \le p$, quando si segna $a_i$, essa deve essere vicina ad $a_{i-1}$.

Due stelle $u$ e $v$ sono vicine se sono direttamente collegate da un arco.

Il giocatore che segna l'ultima stella vince la costellazione. Sapendo che Alice gioca per prima e che entrambi i giocatori giocano in modo ottimale, per ogni $1 \le s \le n$, determina chi vincerà la costellazione.

Input

Ci sono più casi di test. La prima riga dell'input contiene un intero $T$ ($1 \le T \le 100$), che indica il numero di casi di test. Per ogni caso di test:

La prima riga contiene due interi $n$ e $k$ ($2 \le n \le 2 \times 10^3$, $1 \le k < n$), che indicano il numero di stelle e il numero massimo di stelle segnate in ogni turno.

Per le seguenti $(n - 1)$ righe, la $i$-esima riga contiene due interi $u_i$ e $v_i$ ($1 \le u_i, v_i \le n$), che indicano che c'è un arco che collega le stelle $u_i$ e $v_i$.

È garantito che la somma di $n$ su tutti i casi di test non supera $2 \times 10^3$.

Output

Per ogni caso di test, stampa una riga contenente una stringa $d_1 d_2 \cdots d_n$ ($d_i \in \{0, 1\}$), dove $d_i$ indica chi vincerà la costellazione quando $s = i$. Se vincerà Alice, allora $d_i = 1$; altrimenti, se vincerà Bob, allora $d_i = 0$.

Esempio

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

Nota

Il primo caso di test di esempio è illustrato sopra.

• Consideriamo $s = 1$. Nel primo turno, Alice ha tre scelte: segnare $\{2\}$, $\{2, 3\}$ oppure $\{2, 6\}$. Se Alice sceglie $\{2, 6\}$, Bob può poi segnare $\{3\}$, e rimarranno $2$ stelle separate. Nei turni successivi, ogni giocatore può segnare solo una stella, e Bob sarà il vincitore. Le altre scelte di Alice possono essere analizzate allo stesso modo.
• Consideriamo $s = 2$. Nel primo turno, Alice ha cinque scelte: segnare $\{1\}$, $\{3\}$, $\{6\}$, $\{3, 4\}$ oppure $\{3, 5\}$. Alice può scegliere di segnare $\{3\}$, e rimarranno $4$ stelle separate. Nei turni successivi, ogni giocatore può segnare solo una stella, e Alice sarà la vincitrice.

Per il secondo caso di test di esempio, poiché $k = 1$, ci saranno esattamente $3 - 1 = 2$ turni, quindi Bob sarà sempre il vincitore.

Per il terzo caso di test di esempio, se $s = 1$ o $s = 3$, Alice può segnare direttamente le $2$ stelle rimanenti e vincere la costellazione.