#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==
stdin
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