package main

import "fmt"

func main() {
	var T int
	fmt.Scan(&T)
	for tc := 1; tc <= T; tc++ {
		var N, P int
		fmt.Scan(&N, &P)
		G := make([]int, P)
		for i := 0; i < N; i++ {
			var r int
			fmt.Scan(&r)
			G[r%P]++
		}
		g := G[0]
		switch P { // Even in the large case, the P is in [2, 4]
		case 2:
			g += (G[1] + 1) / 2
		case 3:
			min := minInt(G[1], G[2])
			g, G[1], G[2] = g+min, G[1]-min, G[2]-min
			g += (maxInt(G[1], G[2]) + 2) / 3
		case 4:
			g += G[2] / 2
			G[2] %= 2
			min := minInt(G[1], G[3])
			g, G[1], G[3] = g+min, G[1]-min, G[3]-min
			remain := maxInt(G[1], G[3])
			g += remain / 4
			remain %= 4
			if G[2] == 1 && remain == 3 {
				g += 2
			} else if G[2] != 0 || remain != 0 {
				g++
			}
		}
		fmt.Printf("Case #%d: %d\n", tc, g)
	}
}

func minInt(x, y int) int {
	if x < y {
		return x
	}
	return y
}

func maxInt(x, y int) int {
	if x < y {
		return y
	}
	return x
}