LCS Returns

All submissions for this problem are available.
Devu is a freshman in the college. In the data structures course, he has recently learned about LCS (longest common subsequence) problem, He thought about this problem a lot and has finally come up with a challenge for you.
You are given a string S of size N consisting only of lowercase English letters ('a' to 'z'). You have to find minimum length of string V also consisting of lowercase English letters('a' to 'z') such that length of LCS (S, V) ≥ L. The string V should not have more than K consecutive equal characters.
Note that it is not necessary for string V to be composed of characters of S only.
Input
 First line contains T : number of test cases.
 For each test case, You are given two lines.
 First line contains a string S.
 Second line contains two space separated integers K and L.
Output
 For each test case, output a single line containing integer corresponding to the answer of the problem.
Constraints
 1 ≤ T ≤ 10^{6}
 1 ≤ Size of string S ≤ 10^{6}
 1 ≤ Sum of lengths of strings over all test cases ≤ 10^{7}
 1 ≤ K, L ≤ Size of S
Example
Input:
2
aa
1 1
aba
1 2
Output:
1
2
Explanation
 For first test case, V is 'a'.
 For second test case, V can be 'ab' or 'ba'.
Author:  iopc_admin 
Tags  iopc_admin 
Date Added:  28022014 
Time Limit:  2 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP 4.3.2, CPP 4.9.2, GO, JAVA 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
Can you please explain what k
Pls check the test case no.
There seems to be an error in