#include <stdio.h>
#include <algorithm>
using namespace std;

int N, K, age[20], newScheme, newAge[20], maxAge[21];

int gcd (int a, int b){
  int c;
  while(a!=0){ c=a; a=b%a; b=c; }
  return b;
}

void solve(int x, int sum){
  if(x == N){
    for(int i=0; i<N; i++) maxAge[i]=newAge[i];
    newScheme = sum;
    return ;
  }
  if(age[x] <= K){ newAge[x]=age[x]; solve(x+1, sum+age[x]); return ;}
  if(x==0) newAge[x] = age[x];
  else newAge[x] = max(newAge[x-1], age[x]);
  for(; newAge[x] <= maxAge[x+1] && sum+newAge[x] < newScheme; newAge[x]+=K){
    int i;
    for(i=0; i<x; i++) if(gcd(newAge[i], newAge[x]) != K) break;
    if(i==x) solve(x+1, sum+newAge[x]);
  }
}

int main(){
  
  int t, T, i;
  
  scanf("%d", &T);
  for(t=1; t<=T; t++){
    scanf("%d %d", &N, &K);
    int oldScheme = 0;
    for(i=0; i<N; i++){
      maxAge[i] = 1<<30;
      scanf("%d", &age[i]);
      oldScheme += age[i];
    }
    maxAge[N]=1<<30;
    
    sort(age, age+N);

    for(i=0; i<N; i++){
      if(age[i] == 0) if(i || age[N-1] > K) age[i] = K;
      if(age[i] % K) age[i] += K-(age[i]%K);
    }
    newScheme = 1<<30;
    solve(0, 0);
    printf("Case #%d: %d\n", t, newScheme-oldScheme);
  }

  return 0;
}