P - PrekláDka

Náš klient potrebuje v svojom novom sklade s rozmermi 1*N(políčok) rozmiestniť žeriavy tak, aby vedel tovar prepraviť medzi dvomi koncovými polohami. Prekladanie žeriavmi funguje tak, že jeden žeriav tovar zdvihne z nejakého políčka, na ktoré dosiahne a vyloží na iné, tiež ale musí byť v jeho dosahu. Z tohto políčka ho musí vedieť zodvihnúť iný žeriav a posunúť ďalej. Podlaha skladu však nie je práve najkvalitnejšia a niektoré políčka sú natoľko labilné, že neznesú váhu tovaru, tobôž žeriavu. Navyše, políčko, kam sa rozhodnete postaviť žeriav nie je možné použiť ako prekladové.
Klient dostal ponuku výhodne nakúpiť žeriavy s dosahom R, no aj by chcel ušetriť a kúpiť len najmenšie možné množstvo.

Úloha

Pre daný popis skladu a dosah žeriava zistite najmenší počet žeriavov potrebný na preloženie tovaru z prvého políčka na posledné.

Vstup

V prvom riadku súboru sa nachádza číslo Q udávajúce počet sád.

Nasledujú testovacie sady, každá na dvoch samostatných riadkoch.
Prvý riadok obsahuje čísla N a R, druhý reťazec s N znakmi popisujúcimi sklad.

• . znamená voľné políčko
• # znamená labilné políčko

1 ≤ Q ≤ 10
1 ≤ R ≤ 1 000
1 ≤ N ≤ 100 000

Výstup

Výstupom programu je odpoveď na každú sadu na samostatnom riadku. Ak úloha nemá riešenie, vypíšte -1

Príklad

Vstup:

2
16 3
...##..##.##..#.
16 2
..##..##..##..#.

Výstup:

3
-1