잔치 동전

지난 잔치에서 어린 공주가 동전을 아주 많이 받았다. 공주는 아직 어려서 동전의 가치를 모른다. 가치가 5인 동전을 주든 가치가 1인 동전을 주든, 공주에게는 똑같이 동전 한 개다.

다만 가치가 5인 동전과 가치가 1인 동전의 생김새가 다르다는 것은 알아본다. 그래서 가치마다 동전 개수가 모두 같으면 기뻐하고, 하나라도 다르면 기뻐하지 않는다.

공주에게는 여러 가치의 동전이 많이 있다. 이 중에서 일부를 골라 가치의 합이 정확히 $S$가 되게 하려고 한다. 이때 고른 동전에 들어 있는 각 가치의 개수는 모두 같아야 한다. 이런 방법이 몇 가지인지 세어라.

첫 줄에 테스트 케이스의 수 $T$가 주어진다 ($1 \le T \le 100$). 이어서 $T$개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 줄에는 두 정수 $S$와 $N$이 공백 하나로 구분되어 주어진다 ($1 \le S \le 5000$, $1 \le N \le 50$). $S$는 만들어야 하는 가치의 합, $N$은 서로 다른 동전 가치의 개수다.

이어지는 $N$개의 줄에는 각각 두 정수 $V_i$와 $C_i$가 공백 하나로 구분되어 주어진다 ($1 \le V_i, C_i \le 5000$). $V_i$는 동전의 가치, $C_i$는 공주가 가진 그 가치의 동전 개수다. 한 테스트 케이스 안에서 $V_i$는 모두 서로 다르다.

각 테스트 케이스마다 Case n: X 형식으로 한 줄씩 출력한다. $n$은 1부터 시작하는 테스트 케이스 번호이고, $X$는 위 조건을 만족하는 방법의 수다.

어떤 가치의 동전이 쓰인 개수가 하나라도 다르면 두 방법은 서로 다른 방법으로 센다.

답은 항상 64비트 부호 있는 정수 범위에 들어간다.

$S = 10$이고 가치 2인 동전 2개와 가치 6인 동전 1개가 있으면, 합이 10이 되는 조합은 (2, 2, 6) 하나뿐이다. 그런데 가치 2인 동전은 2개, 가치 6인 동전은 1개라서 개수가 같지 않으므로 세지 않는다.

$S = 10$이고 가치 1, 2, 3, 4인 동전이 각각 10개씩 있으면 다음 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).