Feast Coins

At the last feast the young princess received far too many coins. She is very young and does not know what each coin is worth. Hand her a coin of value 5 or a coin of value 1 and she counts each one as a single coin, whatever its value.

She does notice that a coin of value 5 does not look like a coin of value 1. She is happy when she holds the same number of coins of every value she has, and unhappy otherwise.

She owns many coins of different values. She wants to pick some of them so that their values add up to exactly $S$, and so that every value present among the picked coins appears the same number of times. Count how many different ways she has to do this.

The first line contains one integer $T$, the number of test cases ($1 \le T \le 100$). $T$ test cases follow.

Each test case starts with a line holding two integers separated by a single space, $S$ and $N$ ($1 \le S \le 5000$, $1 \le N \le 50$), the required total value and the number of different coin values.

Each of the next $N$ lines holds two integers separated by a single space, $V_i$ and $C_i$ ($1 \le V_i, C_i \le 5000$), the value of a coin and the number of coins of that value the princess owns. Within one test case all $V_i$ are distinct.

For each test case print one line in the form Case n: X, where $n$ is the test case number starting from 1 and $X$ is the number of different ways to reach the total $S$ described above.

Two ways count as different when some coin value appears a different number of times in them.

The answer always fits in a 64-bit signed integer.

With $S = 10$, two coins of value 2 and one coin of value 6, the only combination adding up to 10 is (2, 2, 6). It does not count, because value 2 appears twice while value 6 appears once.

With $S = 10$ and ten coins of each of the values 1, 2, 3 and 4, there are 5 ways: (1, 1, 1, 1, 1, 1, 1, 1, 1, 1), (2, 2, 2, 2, 2), (2, 2, 3, 3), (1, 1, 4, 4), (1, 2, 3, 4).