在上次宴会上，年轻的公主收到了太多的硬币。由于她年纪还小，她不知道每枚硬币的价值。如果你给她一枚价值为 5 的硬币或一枚价值为 1 的硬币，她会认为它们都只是 1 枚硬币，而不考虑其价值。

然而，她能注意到价值为 5 的硬币和价值为 1 的硬币看起来不一样，如果她拥有的每种价值的硬币数量相同，她就会很高兴。否则，她就不会高兴。

她有很多不同价值的硬币，她需要一个硬币子集，使得这些硬币的价值总和恰好为 $S$，并且该子集中每种价值的硬币数量必须相同。你能帮她计算出有多少种不同的方法来实现这一点吗？

输入格式

你的程序将在一个或多个测试用例上进行测试。输入的第一行是一个整数 $T$ ($1 \le T \le 100$)，表示测试用例的数量。接下来是 $T$ 个测试用例。每个测试用例的第一行包含两个由空格分隔的整数 $S$ 和 $N$ ($1 \le S \le 5,000$) ($1 \le N \le 50$)，分别表示所需的总和以及硬币的不同价值数量。接下来有 $N$ 行，每行包含两个由空格分隔的整数 $V_i$ 和 $C_i$ ($1 \le V_i, C_i \le 5,000$)，分别表示某种硬币的价值以及公主拥有的该价值硬币的数量。对于每个测试用例，所有的 $V_i$ 都是不同的。

输出格式

对于每个测试用例，输出一行 “Case n:”（不含引号），其中 $n$ 是测试用例编号（从 1 开始），后跟一个空格，再跟上满足上述条件的组成总和 $S$ 的不同方法数。如果两种方法中任意一种硬币价值出现的次数不同，则认为这两种方法是不同的。

你可以假设结果总是能用 64 位有符号整数表示。

样例

输入 1

2
10 2
2 2
6 1
10 4
1 10
2 10
3 10
4 10

输出 1

Case 1: 0
Case 2: 5

说明

在第一个测试用例中，组成总和 10 的唯一方法是使用硬币子集 (2, 2, 6)，但这不符合要求，因为有 2 枚价值为 2 的硬币和 1 枚价值为 6 的硬币。

在第二个测试用例中，以下是 5 种不同的方法：(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)。