You are given a String S. You can choose any two consecutive characters which are not equal and replace them with any other single character. You can repeat this process atmost K times.
Task
You have to determine the length of the smallest possible string which can be obtained.
Example
Assumption
Approach
Therefore the length of the smallest possible string is 1.
Function description
Complete the solve function provided in the editor. This function takes the following 3 parameters and returns the answer:
Input format
Note: This is the input format that you must use to provide custom input (available above the Compile and Test button).
Output format
For each test case, print in a new line the length of the smallest possible string which can be obtained.
Constraints
1≤T≤100
1≤N,K≤105
S contains only small letter English alphabets.
Code snippets (also called starter code/boilerplate code)
This question has code snippets for C, CPP, Java, and Python.
Note - Use Fast Input/Output Methods for Big Test Cases.
The first line contains the number of test cases, T = 1.
The first test case
Given
Approach
Therefore the length of the smallest possible string is 3.