Background

Special for beginners, ^_^

Description

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.

Format

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.

Samples

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

Limitation

1s, 1024KiB for each test case.