1441 - 街亭之战

Time Limit : 2 Second

Memory Limit : 64 MB

Submission: 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
第十届“北大青鸟”杯浙江师范大学程序设计竞赛
© 2015 HUST ACMICPC TEAM. All Right Reserved.