D Brute

#include <cstdio>
#include <list>
#include <cstring>
#include <string>
#include <queue>
#include <algorithm>
#include <iostream>
#include <cassert>
#include <vector>
using namespace std;
#define REP(i,n) for(int i=0;i<(int)(n);i++)
typedef long long ll;

int nextint()
{
    int t;
    scanf("%d",&t);
    return t;
}

int n,k;
int a[21];
int b[21];
int sum[21];
int res=1000000000;

int gcd(int a, int b)
{
    return b?gcd(b,a%b):a;
}
int iters=0;
void solve(int cur, int prev, int r)
{
    if(r+prev*(n-cur)-sum[cur]>=res) return;
    iters++;
    if(cur==n)
    {
        res=r;
        return;
    }
    for(int j=(max(a[cur],prev)+k-1)/k*k;;j+=k)
    {
//      if(j%k==0)
        {
            b[cur]=j;
            bool ok=true;
            REP(a,cur)
                if(gcd(b[a],j)!=k)
                {
                    ok=false;
                    break;
                }
            if(ok)
                solve(cur+1,j,r+j-a[cur]);
        }
        if(r+j*(n-cur)-sum[cur]>=res) break;
    }
}

int main()
{
    int t;
    scanf("%d",&t);
    for(int test=1;test<=t;test++)
    {
        res=1000000000;
        scanf("%d%d",&n,&k);
        REP(i,n)
            scanf("%d",&a[i]);
        sum[n]=0;
        sort(a,a+n);
        for(int i=n-1;i>=0;i--)
            sum[i]=sum[i+1]+a[i];
        iters=0;
        solve(0,0,0);
        printf("Case #%d: %d\n",test,res);
        fprintf(stderr,"Iters #%d: %d\n",test,iters);
    }
}