#include<iostream>
using namespace std;
#define MAXN 18+1
void next_permutation(int n,int k,int num);
int IsPrime(int n);
int a[MAXN]= {0};
int main() {
	int t,n,k,num=1;
	cin>>t;
	while(t--) {
		cin>>n>>k;
		for(int i=0; i<n; i++) {
			cin>>a[i];
		}

		next_permutation(n,k,num);
		num++;
	}

}

void next_permutation(int n,int k,int num) {
	int solution=0;
	for(int i=1; i<(1<<n); ++i) {
		int cnt=0,sum=0;
		for(int j=0; j<n; j++) {
			if(i&(1<<j)) {
				cnt++;
				sum += a[j];
			}
		}
		if(cnt==k&&IsPrime(sum)) solution++;
		//cout<<endl;
	}
	cout<<"Case #"<<num<<": "<<solution<<endl;
}
int IsPrime(int n) {
	int res=1;
	for(int i=2; i*i<=n; i++) {
		if(n%i==0) res=0;
	}
	return res;
}