#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;
}
 

I2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxhbGdvcml0aG0+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgppbnQgTiwgSywgYWdlWzIwXSwgbmV3U2NoZW1lLCBuZXdBZ2VbMjBdLCBtYXhBZ2VbMjFdOwoKaW50IGdjZCAoaW50IGEsIGludCBiKXsKICBpbnQgYzsKICB3aGlsZShhIT0wKXsgYz1hOyBhPWIlYTsgYj1jOyB9CiAgcmV0dXJuIGI7Cn0KCnZvaWQgc29sdmUoaW50IHgsIGludCBzdW0pewogIGlmKHggPT0gTil7CiAgICBmb3IoaW50IGk9MDsgaTxOOyBpKyspIG1heEFnZVtpXT1uZXdBZ2VbaV07CiAgICBuZXdTY2hlbWUgPSBzdW07CiAgICByZXR1cm4gOwogIH0KICBpZihhZ2VbeF0gPD0gSyl7IG5ld0FnZVt4XT1hZ2VbeF07IHNvbHZlKHgrMSwgc3VtK2FnZVt4XSk7IHJldHVybiA7fQogIGlmKHg9PTApIG5ld0FnZVt4XSA9IGFnZVt4XTsKICBlbHNlIG5ld0FnZVt4XSA9IG1heChuZXdBZ2VbeC0xXSwgYWdlW3hdKTsKICBmb3IoOyBuZXdBZ2VbeF0gPD0gbWF4QWdlW3grMV0gJiYgc3VtK25ld0FnZVt4XSA8IG5ld1NjaGVtZTsgbmV3QWdlW3hdKz1LKXsKICAgIGludCBpOwogICAgZm9yKGk9MDsgaTx4OyBpKyspIGlmKGdjZChuZXdBZ2VbaV0sIG5ld0FnZVt4XSkgIT0gSykgYnJlYWs7CiAgICBpZihpPT14KSBzb2x2ZSh4KzEsIHN1bStuZXdBZ2VbeF0pOwogIH0KfQoKaW50IG1haW4oKXsKICAKICBpbnQgdCwgVCwgaTsKICAKICBzY2FuZigiJWQiLCAmVCk7CiAgZm9yKHQ9MTsgdDw9VDsgdCsrKXsKICAgIHNjYW5mKCIlZCAlZCIsICZOLCAmSyk7CiAgICBpbnQgb2xkU2NoZW1lID0gMDsKICAgIGZvcihpPTA7IGk8TjsgaSsrKXsKICAgICAgbWF4QWdlW2ldID0gMTw8MzA7CiAgICAgIHNjYW5mKCIlZCIsICZhZ2VbaV0pOwogICAgICBvbGRTY2hlbWUgKz0gYWdlW2ldOwogICAgfQogICAgbWF4QWdlW05dPTE8PDMwOwogICAgCiAgICBzb3J0KGFnZSwgYWdlK04pOwoKICAgIGZvcihpPTA7IGk8TjsgaSsrKXsKICAgICAgaWYoYWdlW2ldID09IDApIGlmKGkgfHwgYWdlW04tMV0gPiBLKSBhZ2VbaV0gPSBLOwogICAgICBpZihhZ2VbaV0gJSBLKSBhZ2VbaV0gKz0gSy0oYWdlW2ldJUspOwogICAgfQogICAgbmV3U2NoZW1lID0gMTw8MzA7CiAgICBzb2x2ZSgwLCAwKTsKICAgIHByaW50ZigiQ2FzZSAjJWQ6ICVkXG4iLCB0LCBuZXdTY2hlbWUtb2xkU2NoZW1lKTsKICB9CgogIHJldHVybiAwOwp9Cg==

MjAKMTkgMwo0MyAzOCA0NCA0MyA0IDE2IDEgMyA0MyAzNyA0NiA4IDQ1IDQgNDggMTkgMCA5IDQgCjIwIDEKMSAxIDEgMSAxIDEgMSAxIDEgMSAxIDEgMSAxIDEgMSAxIDEgMSAxCjIwIDgKMzkgMTAgNDAgMjEgMTMgMzEgMjkgMyAyOCAxMiA0OCAxOCA0NyAzMyAxNCA0MiAyNSAxMyAxMyAzNiAKMTkgOAoxNyAzNCA0MSA3IDMwIDIzIDI1IDI4IDE3IDQ2IDQ4IDE2IDQxIDQ4IDQ4IDM1IDQxIDE1IDMyIAoyMCA3CjEyIDM1IDQyIDE1IDIzIDQ1IDIzIDQgMTYgMiA0IDMzIDIgMTIgNDIgOCA2IDQyIDIxIDQwIAoxOSA0CjAgMjQgNDIgNCAxMSAzNSA1MCAyNCAxMSA5IDggMjUgMCAzNyAzNCA4IDI4IDcgMiAKMjAgMQowIDAgMCAwIDAgMCAwIDAgMCAwIDAgMCAwIDAgMCAwIDAgMCAwIDIgCjE4IDE3CjkgMjcgNDggMzggMTIgMTAgNCAzOSAxNyAxOSAyMiA0IDEgMjQgMjIgMjAgMTkgMTggCjEwIDExCjEgMiAzIDQgNSA2IDcgOCA5IDEwIAoyMCA0CjM5IDUgMzIgMjEgOSAyOSAyOCAzMiAzNSA1IDIyIDAgMzggMjEgMjMgNyAyMyAzOSAxNyAxMyAKMTkgNQo0IDEzIDIzIDM3IDUgMzcgMzQgMTAgMjEgNyAyMiA0IDMyIDE4IDcgMzYgNDQgMTAgMzYgCjIwIDEKNTAgNTAgNTAgNTAgNTAgNTAgNTAgNTAgNTAgNTAgNTAgNTAgNTAgNTAgNTAgNTAgNTAgNTAgNTAgNTAgCjIwIDEKMCAwIDAgMCAwIDAgMCAwIDAgMCAwIDAgMCAwIDAgMCAwIDAgMCAwIAoxOSA1CjQ1IDUgMzYgMjIgMTAgNDEgNDAgMzYgMzcgMjEgOSA1IDE4IDI2IDMyIDQ2IDQ2IDQ3IDkgCjE3IDIwCjI5IDQgMCAxMSAxNSAyMSAyNSAxIDM4IDExIDMgNDIgNDkgMTggNDUgNDYgNDQgCjE5IDMKMyAyMiA1MCA0MSAzNCAxMCAzMyA0OSA0MyAzNSAxNyAyMyAxMCAyNyAzMCAyMyA2IDE3IDcgCjE4IDIKMjYgMjQgNyA1IDIgNDUgMzUgMzkgNSAxNCA0MSA1IDQ4IDEzIDExIDIwIDI5IDE4IAoxOSA0CjMgMjIgNTAgMjkgMTggNDIgMzYgMzIgMyA0NCAzMiA0NCAxOSA0MiA3IDUwIDEyIDE5IDM2IAoyIDEKMiAyCjE3IDUKNTAgMTMgNDYgMjkgMjIgMjEgNDIgMzMgNDggMzQgNyAzMyAxNSAxIDIzIDggMzMgCg==

20
19 3
43 38 44 43 4 16 1 3 43 37 46 8 45 4 48 19 0 9 4 
20 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
20 8
39 10 40 21 13 31 29 3 28 12 48 18 47 33 14 42 25 13 13 36 
19 8
17 34 41 7 30 23 25 28 17 46 48 16 41 48 48 35 41 15 32 
20 7
12 35 42 15 23 45 23 4 16 2 4 33 2 12 42 8 6 42 21 40 
19 4
0 24 42 4 11 35 50 24 11 9 8 25 0 37 34 8 28 7 2 
20 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 
18 17
9 27 48 38 12 10 4 39 17 19 22 4 1 24 22 20 19 18 
10 11
1 2 3 4 5 6 7 8 9 10 
20 4
39 5 32 21 9 29 28 32 35 5 22 0 38 21 23 7 23 39 17 13 
19 5
4 13 23 37 5 37 34 10 21 7 22 4 32 18 7 36 44 10 36 
20 1
50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 
20 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
19 5
45 5 36 22 10 41 40 36 37 21 9 5 18 26 32 46 46 47 9 
17 20
29 4 0 11 15 21 25 1 38 11 3 42 49 18 45 46 44 
19 3
3 22 50 41 34 10 33 49 43 35 17 23 10 27 30 23 6 17 7 
18 2
26 24 7 5 2 45 35 39 5 14 41 5 48 13 11 20 29 18 
19 4
3 22 50 29 18 42 36 32 3 44 32 44 19 42 7 50 12 19 36 
2 1
2 2
17 5
50 13 46 29 22 21 42 33 48 34 7 33 15 1 23 8 33