1693 - CHOOSE NUMBER

Time Limit : 1 Second

Memory Limit : 128 MB

Submission: 98

Solved: 21

Description

lxk has n cards and there is a integer number xi on each card. Now his girl lover gives him a card with a number k. She tells lxk to choose k numbers from his cards and the sum of the numbers is a prime number. For example, when n = 4,k = 3, and the set of xi is 3,7,12,19, the only feasible solution is 3 + 7 + 19 = 29. Now you need to calculate how many feasible solutions are there.

Input

First, you will got an integer T, which means the number of tests. There are multiple sets of tests. In each tests, the first line contains two numbers, n and k, and the next line are n numbers xi.


 


1 ≤ n ≤ 18, 1 ≤ k n, 1 ≤ xi ≤ 10000

Output

For each tests, you should first output ”Case #x: ” and then output a number s, which means the number of feasible solution.

sample input
1
4 3
3 7 12 19
sample output
Case #1: 1

hint
source
hexing
© 2015 HUST ACMICPC TEAM. All Right Reserved.