1 #include<stdio.h>
 2 #include<string.h>
 3 int c1[1000],c2[1000],a,b;
 4 
 5 int main(){
 6     int T;
 7     while(scanf("%d",&T)!=EOF){
 8         int n,k;
 9         for(int q=1;q<=T;q++){
10             scanf("%d%d",&n,&k);
11             int i,j,p;
12             memset(c1,0,sizeof(c1));
13             c1[0]=1;int l=0;
14             for(i=1;i<=k;i++){
15                 memset(c2,0,sizeof(c2));
16                 scanf("%d%d",&a,&b);
17                 for(j=0;j<=l;j++){
18                     for(p=1;p<=b;p++){
19                         c2[j+p*a]+=c1[j];
20                     }
21                 }
22                 l+=a*b;
23                 for(j=0;j<=l;j++)c1[j]+=c2[j];
24             }
25             printf("%d\n",c1[n]);
26         }
27 
28     }
29     return 0;
30 }