#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;


int road_repair(vector<int>& arr, int& N, int& K)
{
    sort(arr.begin(), arr.end());
    int len_new = 0, len_pre = 0;
    vector<int> d;
    d.push_back(K);
    for(size_t i = 1; i < arr.size(); i++)
    {
        len_new = d.back() + K;
        for(int j = i-1; j >= 0; j--)
        {
            len_pre = max(K, arr[i] - arr[j] + 1);
            //cout << i << ":" << len_pre << endl;
            if(j > 0)
            {
                len_pre += d[j-1];
            }
            if(len_pre < len_new)
                len_new = len_pre;
        }
        d.push_back(len_new);
        //cout << "d-" << i << ":" << len_new << endl;
    }

    return d.back();
}


int main()
{
    //ifstream file;
    //file.open("sample_input.txt", ios_base::in);

    int num_of_tests;
    cin >> num_of_tests;
    int arr1[] = {1,2,6,9,10,11,12,16};
    //int arr1[] = {402, 444, 322, 123, 302, 183, 380, 80, 200, 533, 299, 147, 89, 28, 268, 181, 404, 270, 432, 236, 525, 316, 487, 412, 241, 33,414, 357, 542, 489, 466, 174, 226, 69, 308, 565, 317, 539, 170, 455};

    for(int i = 0; i < num_of_tests; i++)
    {
        int N, K;
        cin >> N >> K;
        //cout << N << " " << K << endl;
        vector<int> arr;
        int x;
        for(int j = 0; j < N; j++)
        {
            //cin >> x;
            //arr.push_back(x);
            arr.push_back(arr1[j]);
            //cout << x << " ";
        }
        //cout << endl;
        cout << "#" << i+1 << " " << road_repair(arr, N, K) << endl;
    }
    //file.close();

    return 0;
}