1441 - 街亭之战

Time Limit: 2s Memory Limit: 64MB

Submissions: 125 Solved: 65
Description

公元228年春天,诸葛亮出兵伐魏,南安、安定、天水三城望风而降。此后,在军事要地街亭的防守中,诸葛亮没有使用宿将赵云以及魏延,而是使用了虽然智谋过人,与诸葛亮多次英雄所见略同,但缺少临阵经验的马谡。派马谡带领五万多人马做先锋,到军事重镇街亭去抵御魏军。魏国的大将军曹真派张郃为先锋,带领五万人来应敌。 
马谡自小熟谙兵法,军中共有N支分队(N<=20),每支部队已知人数,马谡决定从中挑选K(K<=N)支分队前去抵御魏军。诸葛亮临行前嘱托,部队总人数为素数时,可以摆出八卦阵以制魏军!马谡熟谙兵法,但数学差得很,只知道素数是只能被1和自身整除的数,他请你帮忙计算有多少种调兵遣将的方法可以摆开八卦阵。 
 
观今夜天象,知天下大事。

Input

第一行是测试数据组数T(T<=10),第二行开始,每组测试数据先给出N,K,然后是另起一行N个数字,表示N支部队的人数。

Output

每组测试数据输出一个答案,表示方案种数。

Sample Input
1
5 2
2 3 8 9 999
Sample Output
4
Hint

2+3,2+9,8+9,3+8都是素数

Source
第十届“北大青鸟”杯浙江师范大学程序设计竞赛