Title:  

Description
Princess CC was captured. In order to save her, you have to pass the test of nine levels.

In this pass, you have to pass a floating bridge. The floating bridge consists of several floating planks. Unfortunately, there is a kind of ferocious brocade fish in the water. The sharp thorn of brocade fish will pierce the board. If you walk on the pierced board, you will fall into the water, but you can't swim. Fortunately, you have learned the jumping skill and can jump over multiple boards.

How many times do you have to jump at least to reach the opposite bank without falling into the water?

Input
The first line of input contains a positive integer t (1 < = T < = 100). T represents the number of data groups.

The first row of each set of data includes two integers L (1 < = n < = 1000) and m (1 < = m < = 1000). L represents the number of boards. M represents the number of boards you can skip in a jump. The next line includes a string of length L. counting from the left, bit i of the string is "O", indicating that the ith board is intact, and "X" indicates that the ith board is pierced.

At first you stand on the first board, and your end is the nth board.

The data ensure that the 1st and N th boards are intact.

Output
For each group of data, if the end point can be reached, an integer is output in a separate row to represent the minimum number of jumps required to reach the end point. If the destination cannot be reached, output "- 1" in a separate line.

Sample Input
4
3 1
OXO
3 2
OXO
9 3
OOOXOXOOO
6 2
OXOOXO
Sample Output
1
-1
1
2
HINT
For the first example, you can jump from the first board to the third board.

For the second example, you cannot reach the end.

For the third example, you can go to the third board, then jump to the seventh board, and finally go to the ninth board.

For the fourth example, you can jump to the fourth board, then go to the third board, and finally jump to the sixth board.
 

My thoughts and ideas: I divide all walkable sections and non walkable sections through string processing, then search from the first walkable section to the last walkable section, and record the minimum value with MIN, The judgment method to jump to the nth road section is to judge the number of all grids in the middle of the two road sections and the number of all grids directly in the two road sections plus the length of the two road sections. You can jump in this interval.

Because 1 < = n < = 1000, there are at most 500 walkable sections. There will be a lot of unnecessary judgments in pure search. It should be that it is possible that DUMP has been far less than the length of the section we recorded, but dfs is still traversing whether the subsequent sections can jump, so we can optimize. If (Num > DUMP), we will jump out of the search.

#include<iostream>
#include<string.h>
#include<string>

using namespace std;

int roads[1005];
int za[1005];

int road_num = 0;
int za_num = 0;

int len,dump;

int MIN = __INT32_MAX__;//Record minimum 

void dfs( int now , int end , int dump_num ){
	
	if ( now == end && dump_num < MIN)//Find the end and record 
		MIN = dump_num;
	
	int num = 0;
	
	for ( int k = now + 1 ; k <= end ; k++ ){

        if ( num > dump )
            return; 
		
		num += roads[ k ];
		num += za[ k-1 ];
		
		if ( num + roads[now] >= dump && dump >= num - roads[k] )//If you can jump to the K-th section, jump and continue the search 
			dfs( k , end , dump_num + 1 );
		
	}
	
	return;
	
}

int main(){

	int n;cin>>n;
	
	while( n-- ){
		
		cin>>len>>dump;
		
		MIN = __INT32_MAX__;
		
		memset( za , 0 , sizeof za );
		memset( roads , 0 , sizeof roads );
		
		road_num = 0;
		za_num = 0;
		
		string road;
		cin>>road;
		
		char Now = road[0];
		
		while( road.length() != 0){
			
			for ( int k = 0 ; k < road.length() ; k++ ){
				
				if ( k == road.length() - 1 && road[k] == Now ){
					
					Now=='O'?roads[road_num++] = k + 1:za[za_num++] =  k + 1;
					
					road = "";
					
					break;
					
				}
				if ( road[k] != Now ){
						
					if ( Now == 'O' ){
						roads[road_num++] = k;Now ='X';
					}else{
						za[za_num++] =  k;Now='O';
					}
					
					road = road.substr( k );
					
					break;
					
				}
				
			}
			
		}//Divide all obstacles and walkable sections 
		
		dfs( 0 , road_num - 1 , 0);//Search from segment 0 to the last segment 
		
		if ( MIN == __INT32_MAX__ )
			MIN = -1;
		
		cout<<MIN<<endl;
		
	}
	
	return 0;
	
}