Server Time: Fri Jul 19, 2019 5:41 am
Welcome ( logout
1125 - Divisible Group Sums
  PDF (English) Statistics Forum
Time Limit: 2 second(s) Memory Limit: 32 MB

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 Input

Output for Sample Input

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

 


Problem Setter: Shahriar Manzoor
Special Thanks: Jane Alam Jan (Description, Solution, Dataset)
Developed and Maintained by
JANE ALAM JAN
Copyright © 2012
LightOJ, Jane Alam Jan