PROGRAMMING:Feast Coins
Last feast the young princess received way too many coins. Since she is very young, she doesn’t know the
value of each coin, if you give her a coin with the value 5 or a coin with the value 1, she will consider
them both as just 1 coin, regardless of the value.
However, she can notice that the coin with value 5 doesn’t look the same as the coin with value 1, and
she will be happy if she has the same number of coins of each value. Otherwise, she will not be happy.
She has a lot of coins of different values, and she needs some subset of these coins such that the sum of
their values should be exactly S, and the number of coins of each value in this subset should be the same.
Can you help her to count the number of different ways to do this?
###Input format:
Your program will be tested on one or more test cases. The first line of the input will be a single integer
T (1 ≤ T ≤ 100) representing the number of test cases. Followed by T test cases. Each test case starts
with a line containing two integers separated by a single space S and N (1 ≤ S ≤ 5,000) (1 ≤ N ≤ 50)
representing the total required sum and the number of different values of coins, respectively. Followed by
N lines, each one will contain two integers separated by a single space Vi and Ci (1 ≤ Vi, Ci ≤ 5,000)
representing the value of a coin and the number of coins the princess has with this value, respectively. For
each test case, all values of Vi will be distinct.
###Output format:
For each test case print a single line containing “Case n:” (without quotes) where n is the test case number
(starting from 1) followed by a space then the number of different ways to make the total sum S as
described above. Two ways are considered different if any coin value does not appear the same number of
times in both ways.
You can assume that the result will always fit in a 64-bit signed integer.
###Input example:
Here is a set of inputs. For example:
```in
two
10 2
2 2
6 1
10 4
1 10
2 10
3 10
4 10
```
###Output example:
The corresponding output is given here. For example:
```out
Case 1: 0
Case 2: 5
```
answer：If there is no answer, please comment
value of each coin, if you give her a coin with the value 5 or a coin with the value 1, she will consider
them both as just 1 coin, regardless of the value.
However, she can notice that the coin with value 5 doesn’t look the same as the coin with value 1, and
she will be happy if she has the same number of coins of each value. Otherwise, she will not be happy.
She has a lot of coins of different values, and she needs some subset of these coins such that the sum of
their values should be exactly S, and the number of coins of each value in this subset should be the same.
Can you help her to count the number of different ways to do this?
###Input format:
Your program will be tested on one or more test cases. The first line of the input will be a single integer
T (1 ≤ T ≤ 100) representing the number of test cases. Followed by T test cases. Each test case starts
with a line containing two integers separated by a single space S and N (1 ≤ S ≤ 5,000) (1 ≤ N ≤ 50)
representing the total required sum and the number of different values of coins, respectively. Followed by
N lines, each one will contain two integers separated by a single space Vi and Ci (1 ≤ Vi, Ci ≤ 5,000)
representing the value of a coin and the number of coins the princess has with this value, respectively. For
each test case, all values of Vi will be distinct.
###Output format:
For each test case print a single line containing “Case n:” (without quotes) where n is the test case number
(starting from 1) followed by a space then the number of different ways to make the total sum S as
described above. Two ways are considered different if any coin value does not appear the same number of
times in both ways.
You can assume that the result will always fit in a 64-bit signed integer.
###Input example:
Here is a set of inputs. For example:
```in
two
10 2
2 2
6 1
10 4
1 10
2 10
3 10
4 10
```
###Output example:
The corresponding output is given here. For example:
```out
Case 1: 0
Case 2: 5
```
answer：If there is no answer, please comment