题目描述

Xavier，a 9-year-old student，loves playing many kinds of puzzles．One of his favourites is the following：
Xerier，his classmate，has made many cards．She writes down a single positive number on each of them．No numbers written on different cards are the same．After that she writes down an equation，whose right side is a single positive number chosen by her，and the left side is the sum of $p$ integers：
Then she asks Xavier put $p$ cards on the corresponding $X_i$’s position to make this equation correct，with an additional condition that $X_i$ should be ordered from smaller to bigger，i.e．
Every time Xavier immediately comes up with many solutions．Now he wants to know how many solutions in total are there for any $n$ given by Xerier．

输入格式

There are multiple test cases．The number of them is given in the beginning of the input．Then a series of input block comes one by one．
For each test case：
The first line contains two space-separated integers $m$ and $p$．The second line contains $m$ distinct positive integers － the numbers written on each of the cards．None of these integers exceeds $13000$．
There are about $120$ test cases in total，but $90\%$ of them are relatively small．More precisely，all numbers are less than or equal to $100$ in $90\%$ of the test cases．

输出格式

For each test case：
For each positive integer，output the number of ways in a single line．To keep the output finite，only numbers with positive ways should be outputted．
Output a blank line after each test case．See sample for more format details．

3
3 3
1 2 3
5 4
1 3 5 6 7
10 3
1 2 3 4 5 6 7 8 9 10

Case #1:
6: 1
Case #2:
15: 1
16: 1
17: 1
19: 1
21: 1
Case #3:
6: 1
7: 1
8: 2
9: 3
10: 4
11: 5
12: 7
13: 8
14: 9
15: 10
16: 10
17: 10
18: 10
19: 9
20: 8
21: 7
22: 5
23: 4
24: 3
25: 2
26: 1
27: 1

数据规模与约定

$100\%$ 的数据满足：$1 \le p \le 5$。

题目来源

Acm 2011 上海