#include <cstdio>

 #include <cstring>

 #include <algorithm>

 #define maxn 3000

 using namespace std;

 int dp[maxn];

 int a,b;

 int t,n,k;

 int main()

 {

     scanf("%d",&t);

     while(t--)

     {

         scanf("%d%d",&n,&k);

         memset(dp,,sizeof(dp));

         dp[]=;

         for(int i=; i<=k; i++)

         {

             scanf("%d%d",&a,&b);

             for(int j=n; j>=a; j--)

             {

                 for(int x=; x<=b; x++)

                 {

                     if(j-x*a>=)

                     {

                         dp[j]+=dp[j-x*a];

                     }

                 }

             }

         }

         printf("%d\n",dp[n]);

     }

     return ;

 }