XC - Xavier is Learning to Count

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 Xi's position to make this equation correct, with an additional condition that Xi 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.

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.

Example

Input:
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

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

This problem has 82 submissions during the onsite contest, but none of them gets Accepted.


Added by:Fudan University Problem Setters
Date:2011-10-10
Time limit:7s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:ACM/ICPC Regional Contest, Shanghai 2011; Problem Setter: Blue Mary; Special Thanks: Gustav Matula

hide comments
2011-10-27 08:43:16 Bin Jin
float-point operations are rather slow on SPOJ
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.