«Astra» — это красивая настольная игра, в которой игроки по очереди открывают созвездия, отмечая звёзды. Эта игра представляет собой искусное сочетание тактики и стратегии с простым и интуитивно понятным набором правил, благодаря которому её легко освоить и быстро разыграть.

Photo by @kavics004 on BoardGameGeek

Рассмотрим игру для двух игроков между Алисой и Бобом. В этой игре есть древовидное созвездие, которое можно рассматривать как связный граф, состоящий из $n$ звёзд (пронумерованных от $1$ до $n$) и $(n - 1)$ рёбер. В самом начале отмечена только одна звезда $s$. Алиса и Боб по очереди отмечают оставшиеся звёзды по следующему правилу:

• В каждый ход игрок должен отметить хотя бы $1$ звезду и не более $k$ звёзд.
• Каждую звезду можно отметить только один раз.
• Пусть $a_1, a_2, \cdots, a_p$ — звёзды, отмеченные за один ход, в порядке их отмечания:
  • При отмечании $a_1$ она должна быть соседом некоторой уже отмеченной звезды.
  • Для всех $2 \le i \le p$, при отмечании $a_i$ она должна быть соседом $a_{i-1}$.

Две звезды $u$ и $v$ называются соседями, если они напрямую соединены ребром.

Игрок, отметивший последнюю звезду, выигрывает созвездие. Считая, что Алиса ходит первой и оба игрока играют оптимально, для каждого $1 \le s \le n$ определите, кто выиграет созвездие.

Входные данные

Входные данные состоят из нескольких тестовых наборов. Первая строка входных данных содержит целое число $T$ ($1 \le T \le 100$), обозначающее количество тестовых наборов. Для каждого тестового набора:

Первая строка содержит два целых числа $n$ и $k$ ($2 \le n \le 2 \times 10^3$, $1 \le k < n$), обозначающих количество звёзд и максимальное количество звёзд, которые можно отметить за один ход.

В следующих $(n - 1)$ строках $i$-я строка содержит два целых числа $u_i$ и $v_i$ ($1 \le u_i, v_i \le n$), обозначающих наличие ребра, соединяющего звёзды $u_i$ и $v_i$.

Гарантируется, что сумма $n$ по всем тестовым наборам не превышает $2 \times 10^3$.

Выходные данные

Для каждого тестового набора выведите одну строку, содержащую строку $d_1 d_2 \cdots d_n$ ($d_i \in \{0, 1\}$), где $d_i$ указывает, кто выиграет созвездие при $s = i$. Если выиграет Алиса, то $d_i = 1$; иначе, если выиграет Боб, то $d_i = 0$.

Пример

Входные данные 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

Выходные данные 1

011000
000
101

Примечание

Первый тестовый набор из примера проиллюстрирован выше.

• Рассмотрим $s = 1$. На первом ходу у Алисы есть три варианта: отметить $\{2\}$, $\{2, 3\}$ или $\{2, 6\}$. Если Алиса выберет $\{2, 6\}$, Боб затем может отметить $\{3\}$, и останется $2$ разъединённые звезды. На следующих ходах каждый игрок сможет отмечать только по одной звезде, и победителем станет Боб. Другие варианты хода Алисы анализируются аналогично.
• Рассмотрим $s = 2$. На первом ходу у Алисы есть пять вариантов: отметить $\{1\}$, $\{3\}$, $\{6\}$, $\{3, 4\}$ или $\{3, 5\}$. Алиса может выбрать $\{3\}$, и останется $4$ разъединённые звезды. На следующих ходах каждый игрок сможет отмечать только по одной звезде, и победительницей станет Алиса.

Во втором тестовом наборе из примера, так как $k = 1$, будет ровно $3 - 1 = 2$ хода, поэтому Боб всегда выигрывает.

В третьем тестовом наборе из примера, если $s = 1$ или $s = 3$, Алиса может сразу отметить оставшиеся $2$ звезды и выиграть созвездие.