AMR12I  Saruman of Many Colours
'"For I am Saruman the Wise, Saruman Ringmaker, Saruman of Many Colours!"
'I looked then and saw that his robes, which had seemed white, were not so, but were woven of all colours. And if he moved they shimmered and changed hue so that the eye was bewildered.'  Gandalf the Grey.
And so it was that Saruman decided to brand his Urukhai army with the many colours that he fancied. His method of branding his army was as follows.
He straps his army of N Urukhai onto chairs on a conveyor belt. This conveyor belt passes through his colouringroom, and can be moved forward or backward. The Urukhai are numbered 0 to N1 according to the order in which they are seated. Saruman wishes that the i'th Urukhai be coloured with the colour c[i].
Further, his colouringroom has space for exactly K chairs. Once the chosen K consecutive Urukhai are put into the room, a colour jet sprays all K of them with any fixed colour. The conveyor belt is not circular (which means that the N1'th and the 0'th Urukhai are not consecutive). Note that Urukhai can be recoloured in this process.
Saruman wants to find out what is the minimum number of times that the jet needs to be used in order to colour his army in the required fashion. If it is not possible to colour the army in the required fashion, output 1.
Input (STDIN):
The first line contains the number of testcases T.
Each test case consists of 2 lines. The first line contains two spaceseparated integers, N and K.
This is followed by a single like containing a string of length N, describing the colours of the army. The i'th character of the string denotes the colour of the i'th Urukhai in the army.
Output (STDOUT):
Output T lines, one for each test case containing the answer for the corresponding test case. Remember if it is not possible to colour the army as required, output 1.
Constraints:
1 <= T <= 50
1 <= K <= N <= 20,000
The string c has length exactly N and contains only the characters 'a',...,'z'.
Sample Input:
2
3 2
rgg
3 3
rgg
Sample Output:
2
1
Notes/Explanation of Sample Input:
In the first test case, soldiers 0 and 1 can first be painted with 'r', and then soldiers 1 and 2 can be painted with 'g'.
In the second test case, since N = K, all the soldiers will only have the same color.
hide comments
rahul gautam:
20150913 14:40:27
The rings were created by sauron :P 

dark_lord1:
20150818 18:43:33
@Aditya Bahuguna you saved me a lot of time..but I still feel that I did not get to clear my concept myself rather than took the help of comments. 

[deleted]:
20131207 23:42:54
@varun even without following a proper algorithm as required by the question,solution is getting accepted.please check the test cases 

Ayush Vatsa:
20131206 06:06:47
nice problem...had fun 

Aditya Bahuguna:
20130602 11:08:29
@those gettng WA:


Atul Kumar Verma:
20130517 19:39:43
Plzz give some tricky cases i am getting wrong ans. 

mehmetin:
20130102 10:31:34
nice problem Last edit: 20130103 02:57:25 

Shashank_Jain:
20121229 19:48:39
@nightmare  thanks mate ! i thought we can only start from 1 .. well this wasn't given . thanks :) 

foreverbell:
20121229 09:57:20
@Flawless: paint it in the reverse order. 

Shashank_Jain:
20121229 08:56:30
@varun jalan i think david is right.. u can't paint last one "g".. or can u ??? Last edit: 20121229 08:56:48 
Added by:  Varun Jalan 
Date:  20121222 
Time limit:  2s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Varun Jalan  ICPC Asia regionals, Amritapuri 2012 