Fyrir framan Yuki er furðuleg gangbraut.

Hægt er að líta á þessa gangbraut sem tré með $n$ hnútum. $i$-ti leggurinn tengir hnút $u_i$ og hnút $v_i$. Hver hnútur er litaður annaðhvort svartur eða hvítur, sem lýst er með tvíundarstreng $s$ af lengd $n$:

• Ef $s_i=0$ er liturinn á hnúti $i$ svartur.

• Ef $s_i=1$ er liturinn á hnúti $i$ hvítur.

Yuki hefur stökkgetu $k$, sem þýðir að þegar hún er í hnúti $x$ getur hún stokkið í hvaða hnút $y$ sem er þannig að $\operatorname{dist}(x,y)\le k$. Hér táknar $\operatorname{dist}(x,y)$ fjölda leggja á einfalda veginum milli hnúts $x$ og hnúts $y$.

Næst mun Yuki framkvæma $n-1$ umferðir af stökkum á gangbrautinni. Í $i$-tu umferðinni byrjar Yuki í hnúti $1$ og vill komast í hnút $i+1$ með runu af stökkum. Á sama tíma vill Yuki lágmarka fjölda skipta sem hún lendir á svörtum hnúti eftir stökkin sín.

Þú þarft að hjálpa Yuki að finna lágmarksfjölda skipta sem hún lendir á svörtum hnúti fyrir hverja umferð af stökkum.

Inntak

Þetta verkefni inniheldur mörg prófunartilvik.

Fyrsta línan inniheldur jákvæða heiltölu $t$ ($1\le t\le 10^5$), sem táknar fjölda prófunartilvika.

Fyrir hvert prófunartilvik:

• Fyrsta línan inniheldur tvær jákvæðar heiltölur $n,k$ ($1\le n\le 5\cdot 10^5$, $1\le k\le n$).

• Önnur línan inniheldur tvíundarstreng $s$ af lengd $n$ ($s_i\in\{0,1\}$).

• Næstu $n-1$ línur innihalda hver um sig tvær jákvæðar heiltölur $u_i,v_i$ ($1\le u_i,v_i\le n$, $u_i\ne v_i$).

Tryggt er að summa $n$ yfir öll prófunartilvik fari ekki yfir $5\cdot 10^5$.

Úttak

Fyrir hvert prófunartilvik skal prenta eina línu sem inniheldur $n-1$ heiltölur, þar sem $i$-ta heiltalan táknar lágmarksfjölda skipta sem Yuki lendir á svörtum hnúti í $i$-tu umferðinni af stökkum.

Dæmi

Dæmi um inntak 1

2
5 1
01010
3 5
2 1
1 3
3 4
9 3
100010000
1 2
2 3
2 4
3 5
3 6
4 7
6 8
7 9

Dæmi um úttak 1

0 1 1 2
1 1 1 0 1 1 1 2

Athugasemd

Fyrir fyrra prófunartilvikið:

• Fyrir $1$. umferðina af stökkum er ein gild runa heimsóttra hnúta $1,2$.

• Fyrir $4$. umferðina af stökkum er ein gild runa heimsóttra hnúta $1,3,5$.

Fyrir seinna prófunartilvikið:

• Fyrir $4$. umferðina af stökkum er ein gild runa heimsóttra hnúta $1,5$.

• Fyrir $7$. umferðina af stökkum er ein gild runa heimsóttra hnúta $1,5,8$.

• Fyrir $8$. umferðina af stökkum er ein gild runa heimsóttra hnúta $1,4,9$.