Time Limit: 1000 mSec Memory Limit : 32768 KB

As we all known, merge sort is an O(nlogn) comparison-based sorting algorithm. The merge sort achieves its good runtime by a divide-and-conquer strategy, namely, that of halving the list being sorted: the front and back halves of the list are recursively sorted separately, then the two results are merged into the answer list. An implementation is shown as follows:

The *procedure* Merge(L1,L2:*in* List_type;L:*out* List_type) that we have in mind for sorting two lists is described as follows. Initialize pointers to the first item in each list L1,L2, and then

*repeat*

compare the two items pointed at;

move the smaller into L;

move the pointer which originally points at the smaller one to the next number;

*until* one of L1,L2 exhausts;

drain the remainder of the unexhausted list into L;

Now let us come to the situation when there are k pointers, here k≥2. Let L be a list of n elements. Divide L into k disjoint contiguous sublists L_{1},L_{2},…,L_{k} of nearly equal length. Some L_{i}’s (namely, n reminder k of them, so possibly none) will have length , let these have the low indices: L_{1},L_{2},…,L_{n%k} Other L_{i}’s will have length , and high indices are assigned: L_{n%k+1},…,L_{k-1},L_{k}. We intend to recursively sort the L_{i}’s and merge the k results into an answer list.

We use Linear-Search-Merge here to merge k sorted lists. We find the smallest of k items (one from each of the k sorted source lists), at a cost of k-1 comparisons. Move the smallest into the answer list and advances its corresponding pointer (the next smallest element) in the source list from which it came. Again there are k items, from among which the smallest is to be selected. (When i (1 ≤ i < k) lists are empty, k-way merging sort becomes to (k-i)-way merging sort, and the draining process will start when the total order of all the elements have been found)

Given a list containing n elements, your task is to find out the maximum number of comparisons in k-way merging sort.

The first line of the input contains an integer T (T <= 100), indicating the number of cases. Each case begins with a line containing two integer n (1 ≤ n ≤ 10^{100}) and k (2 ≤ k ≤ 20), the number of elements in the list, and it is k-way merging sort.

For each test case, print a line containing the test case number (beginning with 1) and the maximum number of comparisons in k-way merging sort.

4
2 2
3 2
100 7
1000 10

Case 1: 1
Case 2: 3
Case 3: 1085
Case 4: 22005