לפני Yuki נמצא מעבר חצייה מוזר.

אפשר לראות במעבר חצייה זה עץ בעל $n$ צמתים. הקשת ה-$i$ מחברת את הצומת $u_i$ לצומת $v_i$. כל צומת צבוע בשחור או בלבן, כפי שמתואר במחרוזת בינארית $s$ באורך $n$:

• אם $s_i=0$, צבע הצומת $i$ הוא שחור.

• אם $s_i=1$, צבע הצומת $i$ הוא לבן.

ל-Yuki יש יכולת קפיצה $k$, כלומר כשהיא בצומת $x$ היא יכולה לקפוץ לכל צומת $y$ המקיים $\operatorname{dist}(x,y)\le k$. כאן $\operatorname{dist}(x,y)$ מציין את מספר הקשתות במסלול הפשוט בין הצומת $x$ לצומת $y$.

כעת Yuki תבצע $n-1$ סבבי קפיצות על מעבר החצייה. בסבב ה-$i$ היא מתחילה בצומת $1$ ורוצה להגיע לצומת $i+1$ באמצעות סדרת קפיצות. בה בעת היא רוצה למזער את מספר הפעמים שהיא נוחתת על צומת שחור לאחר קפיצותיה.

עליך לעזור ל-Yuki למצוא את מספר הנחיתות המזערי על צומת שחור בכל סבב קפיצות.

קלט

בעיה זו מכילה מספר מקרי בדיקה.

השורה הראשונה מכילה מספר שלם חיובי $t$ ($1\le t\le 10^5$), המציין את מספר מקרי הבדיקה.

לכל מקרה בדיקה:

• השורה הראשונה מכילה שני מספרים שלמים חיוביים $n,k$ ($1\le n\le 5\cdot 10^5$, $1\le k\le n$).

• השורה השנייה מכילה מחרוזת בינארית $s$ באורך $n$ ($s_i\in\{0,1\}$).

• כל אחת מ-$n-1$ השורות הבאות מכילה שני מספרים שלמים חיוביים $u_i,v_i$ ($1\le u_i,v_i\le n$, $u_i\ne v_i$).

מובטח שסכום ערכי $n$ בכל מקרי הבדיקה אינו עולה על $5\cdot 10^5$.

פלט

לכל מקרה בדיקה יש להדפיס שורה אחת ובה $n-1$ מספרים שלמים, כאשר המספר ה-$i$ מציין את מספר הפעמים המזערי שבהן Yuki נוחתת על צומת שחור בסבב הקפיצות ה-$i$.

דוגמאות

קלט 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

פלט 1

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

הערה

למקרה הבדיקה הראשון:

• בסבב הקפיצות ה-$1$, סדרה אפשרית של צמתים שבהם מבקרים היא $1,2$.

• בסבב הקפיצות ה-$4$, סדרה אפשרית של צמתים שבהם מבקרים היא $1,3,5$.

למקרה הבדיקה השני:

• בסבב הקפיצות ה-$4$, סדרה אפשרית של צמתים שבהם מבקרים היא $1,5$.

• בסבב הקפיצות ה-$7$, סדרה אפשרית של צמתים שבהם מבקרים היא $1,5,8$.

• בסבב הקפיצות ה-$8$, סדרה אפשרית של צמתים שבהם מבקרים היא $1,4,9$.