New update is available. Click here to update.

Task Scheduler

Posted: 6 Jan, 2021
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

A ninja needs to complete ‘n’ tasks. Each task is represented by an uppercase letter of the English alphabet. Different letters are assigned to different tasks. A ninja can complete tasks in any order. He takes one unit of time to complete one task. For each unit of time, he could complete either one task or just be idle.

Ninja easily gets bored by doing the same task again. So he decided to keep at least ‘t’ units of time between any two same tasks.

You are given a string ‘tasks’ consisting of ‘n’ uppercase letters of the English alphabet, representing the tasks ninja need to complete, and an integer ‘t’ representing the least units of time between any two same tasks. Find out the minimum total units of time ninja will take to complete all ‘n’ tasks.

Input Format :
The first line of input contains an integer ‘T’ denoting the number of test cases.

The first line of each test case contains two space-separated integers ‘n’ and ‘t’; representing the number of tasks and the least units of time between any two same tasks respectively.

The second line of the test case contains a string ‘tasks’ consisting of the ‘n’ uppercase character of the English alphabet.
Output Format :
For each test case, print the minimum total units of time ninja will take to complete all ‘n’ tasks.

Print the output of each test case in a new line.
Note :
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints :
1 <= T <= 50
1 <= n <= 10^4
1 <= t <= 100

Where ‘T’ is the number of test cases and ‘n’ is the number of tasks and ‘t’ is the least units of time between any two same tasks.

Time Limit : 1 sec