"For I am Saruman the Wise, Saruman Ring-maker, 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 Uruk-hai army with the many colours that he fancied. His method of branding his army was as follows.

He straps his army of N Uruk-hai onto chairs on a conveyor belt. This conveyor belt passes through his colouring-room, and can be moved forward or backward. The Uruk-hai are numbered 0 to N-1 according to the order in which they are seated. Saruman wishes that the i'th Uruk-hai be coloured with the colour c[i].

Further, his colouring-room has space for exactly K chairs. Once the chosen K consecutive Uruk-hai 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 N-1'th and the 0'th Uruk-hai are not consecutive). Note that Uruk-hai 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

The first line contains the number of test-cases T.

Each test case consists of 2 lines. The first line contains two space-separated 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 Uruk-hai in the army.

Output

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

Output:
2
-1

Explanation of Sample

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.