In some file systems, the disk space used by a file is not always equal to the file's size. This is because the disk is divided into clusters of equal size, and each cluster can only be used by a single file. For example, if the cluster size is 512 bytes, and we have a file of size 600 bytes, it would have to be stored in two clusters. Those two clusters cannot be shared with any other files, so the file ends up using 1024 bytes of disk space.

Note that we don't need any clusters for a file of size 0.

Given N single files and the cluster size, you have to print the total disk space used by the given files.

Input

The first line of input will contain T denoting the number of test cases. The first line of each test case contains two integers N, denoting the number of files and S, denoting the cluster size of the file system. The second line of each test case contains N integers a_i (1 <= i <= N) denoting the size of the ith file.

Constraints:

1 <= T <= 1000
1 <= N <= 100
1 <= S <= 1048576
0 <= a_i <= 10^9

Output

For each test case print a single line containing “Case X: S” without the quotes, where X is the case number and S is the total disk space used by the given files.

Example

Input:
2
1 512
600
4 32768
16 32 128 128

Output:
Case 1: 1024
Case 2: 131072