提示: 欢迎访问OurACM平台。
Problem 1979 Reverse the prefix

Accept: 195    Submit: 649
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

Given a string with uppercase letters, and you are allowed to reverse the prefix by each operation. Your task is to make the string to become the smallest one in alphabetical order at most k operations. You should note that the length of the prefix you want to reverse must be larger than the previous operation except the first operation.

For example, given the string "BCDAF", and you are allowed to operate at most 2 times. If you reverse the prefix of length 3 ("BCD") to get "DCBAF", and then the length of the prefix you reverse next time should be larger than 3. After reversing the prefix of length 4 ("DCBA") to get "ABCDF", and it's the smallest one in alphabetical order.

Input

The first line of the input contains an integer T (T≤50), indicating the number of cases. Each case begins with a line containing two integers N and k (0<N≤100, 0≤k≤N), the length of the string and the maximum times of operations you are allowed to do. The next line contains the string, consisting of characters 'A' to 'Z'.

Output

For each test case, print a line containing the test case number (beginning with 1) and the smallest string you make in alphabetical order.

Sample Input

2 5 1 BCDAF 5 2 BCDAF

Sample Output

Case 1: ADCBF Case 2: ABCDF

Source

The 35th ACM/ICPC Asia Regional Fuzhou Site —— Online Contest

Submit  Back  Status  Discuss