Xavier is Learning to Count

Time Limit: 4000 ms Memory Limit: 65536 KiB

Problem Description

      Xavier, a 9-year-old student, loves playing many kinds of puzzles. One of hisfavourites 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:
                           X1 + X2 + … + X p = n
      Then she asks Xavier put p cards on the corresponding Xi’s position to make
this equation correct, with an additional condition that Xi should be ordered from
smaller to bigger, i.e.
                            X i < X i+1 , ∀1 ≤ i < p
       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.
 

Input

 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 (1<=p<=5). 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.

Output

 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.
 

Sample Input

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

Sample Output

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

Hint

 

Source

2011 The 36th ACM-ICPC Asia Shanghai Regional Contest - hosted by Fudan University