Late autumn. The cold wind blew away the last traces of summer heat and stripped the leaves from the bushes at the foot of the banyan tree. Evan and Lyra, who had known each other for years, returned once again to the lush banyan tree where they had met as children. The stream remained the same, the stone bridge remained the same, and the banyan tree, despite the cycles of growth and decay, still stood tall and canopy-like. Yet, Evan and Lyra were no longer the carefree youths they had been seven or eight years ago.

...

"It's almost deep winter, and the banyan tree's leaves haven't fallen yet..."

"The banyan is an evergreen; you won't see a distinct season of falling leaves..."

"Sigh... I can't believe it's been seven years. The banyan is still the same banyan, but you are no longer the same you..."

"Actually, what is there that remains unchanged? The banyan is evergreen, and the macroscopic eternity of its emerald canopy is composed of the constant growth and decay of countless tiny leaves. In the passage of time, everything is constantly changing..."

"But look at this banyan, day after day, season after season, year after year, as if it were eternal, with its tangled roots and lush foliage. I'm thinking, perhaps it would be better to be a tree, letting time flow through the branches and leaves, while I just guard this patch of shade."

"The banyan is indeed long-lived, but in this infinite span of time, it will eventually vanish into dust. Rather than being like a banyan, rooted in a patch of soil to feel the changing of the seasons year after year, it would be better to see as much of the world as possible in the limited time we have. Besides, although the banyan grows slowly, it still puts out a new branch every spring to explore outward..."

"Really? In its long life, does the banyan explore outward step by step like that?"

"After all, even if the canopy looks unchanged, the banyan changes with the cycles of time. When spring arrives, it is naturally time for growth, and it should respond accordingly..."

"Compared to the instinctive growth in response to the changing seasons, I would rather believe that the banyan has an active, exploring heart."

"Actually, the banyan does have a heart. When the banyan is first planted, the heart sprouts at the roots. Every spring thereafter, when the banyan grows new branches, the heart moves a little toward the direction of the new branches, so it can get closer to the outside world. Look at these branches overhead, crisscrossing; in fact, the heart has been moving among these branches for decades..."

"Wow, so you mean that somewhere in this dense thicket of branches, the heart of this banyan is hidden?"

"That's right, but to know where it is, you have to put in some extra effort..."

"Ah, thinking about it now, a tree is still not as good as a person... like you, if I were to lean in like this, I could hear the heartbeat..."

...

A banyan tree can be abstracted as a rooted tree with $n$ nodes, where the nodes are numbered $1 \sim n$, and node $1$ is the root. Initially, the tree consists only of node $1$, and the heart is also at node $1$. In each subsequent step, the tree grows a new node: a node adjacent to one of the nodes already present in the tree is added. After this, the heart moves one step along the simple path from its current position to the newly added node. There are many possible growth sequences for this $n$-node tree, and different sequences may result in different final positions for the heart. Now, Evan and Lyra want to know which nodes could possibly be the final position of the heart when the growth process ends.

For example, for a tree of size $4$ with edges $\{\left< 1,2 \right> , \left< 1,3 \right> , \left< 1,4 \right> \}$, there are three different growth sequences that allow the heart to end up at nodes $2, 3,$ and $4$ respectively:

Ending at node $2$: 1. Grow $3$ from $1$, heart moves from $1$ to $3$. 2. Grow $4$ from $1$, heart moves from $3$ back to $1$. 3. Grow $2$ from $1$, heart moves from $1$ to $2$.

Ending at node $3$: 1. Grow $2$ from $1$, heart moves from $1$ to $2$. 2. Grow $4$ from $1$, heart moves from $2$ back to $1$. 3. Grow $3$ from $1$, heart moves from $1$ to $3$.

Ending at node $4$: 1. Grow $2$ from $1$, heart moves from $1$ to $2$. 2. Grow $3$ from $1$, heart moves from $2$ back to $1$. 3. Grow $4$ from $1$, heart moves from $1$ to $4$.

We can prove that there is no possible growth sequence that allows the heart to end up at node $1$.

Input

Read from standard input.

The first line contains two positive integers $W$ and $T$, representing the subtask number (in the sample, $W=0$) and the number of test cases, respectively. The following lines describe $T$ test cases. For each test case:

The first line contains a positive integer $n$, the number of nodes in the tree.

The next $n-1$ lines each contain two positive integers $a_i, b_i$, representing an edge between nodes $a_i$ and $b_i$. It is guaranteed that $a_i \neq b_i$ and the $n-1$ edges form a tree.

Output

Output to standard output.

If $W \neq 3$, for each test case, output a single line containing a $01$ string of length $n$, where the $i$-th character indicates whether it is possible for the heart to end at node $i$ ($1$ for possible, $0$ for impossible).

If $W = 3$, for each test case, output a single character representing the answer for node $1$.

Examples

Input 1

0 3
4
1 2
1 3
1 4
6
1 2
1 3
1 4
4 5
5 6
10
1 2
1 3
3 4
3 5
3 6
4 7
7 8
8 9
9 10

Output 1

0111
000101
0000001010

Note

This is not a very difficult problem.

Constraints

Subtask 1 [10pts]

$T \leq 50; n \leq 15$.

Subtask 2 [10pts]

$T \leq 20; n \leq 10^5$. Except for node $1$, the degree of each node (including its parent) does not exceed $2$.

Subtask 3 [10pts]

$T \leq 200; n \leq 100$. Only output a single character for the answer of node $1$, i.e., it is guaranteed that the answer for node $1$ is correct.

Subtask 4 [35pts]

$T \leq 20; n \leq 10^3$.

Subtask 5 [35pts]

$T \leq 20; n \leq 10^5$.