Given a list of N numbers you will be allowed to choose any M of them. So you can choose in NCM ways. You will have to determine how many of these chosen groups have a sum, which is divisible by D.
Input
Input starts with an integer T (≤ 20), denoting the number of test cases.
The first line of each case contains two integers N (0 < N ≤ 200) and Q (0 < Q ≤ 10). Here N indicates how many numbers are there and Q is the total number of queries. Each of the next N lines contains one 32 bit signed integer. The queries will have to be answered based on these N numbers. Each of the next Q lines contains two integers D (0 < D ≤ 20) and M (0 < M ≤ 10).
Output
For each case, print the case number in a line. Then for each query, print the number of desired groups in a single line.
Sample
| Sample Input | Sample Output |
|---|---|
2 10 2 1 2 3 4 5 6 7 8 9 10 5 1 5 2 5 1 2 3 4 5 6 6 2 | Case 1: 2 9 Case 2: 1 |