#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<algorithm>
#include<cstring>
using namespace std;
const int mx=200,my=200,tim=50,mo=1000000007;
const int d[8][2]={1,2,-1,2,1,-2,-1,-2,2,1,-2,1,-2,-1,2,-1};
int x,y,n,bfs[mx*my*4][2],a[mx*2][my*2],i,l,r,xx,yy,cnt[tim+10];
long long K;
int main(){
    int t;
    scanf("%d",&t);
    while(t--)
    {
        memset(bfs,0,sizeof(bfs));
        memset(a,0,sizeof(a));
        memset(cnt,0,sizeof(cnt));
    scanf("%I64d%d",&K,&n);
    for(i=1;i<=n;++i)scanf("%d%d",&x,&y),a[x+mx][y+my]=-1;
    a[mx][my]=1;
    bfs[l=r=1][0]=mx; bfs[1][1]=my;
    while(l<=r){
        x=bfs[l][0]; y=bfs[l++][1];
        if(a[x][y]==K+1 || a[x][y]==tim+1)break;
        for(i=0;i<8;++i){
            xx=x+d[i][0]; yy=y+d[i][1];
            if(!a[xx][yy]){
                a[xx][yy]=a[x][y]+1;
                cnt[a[xx][yy]]++;
                bfs[++r][0]=xx;
                bfs[r][1]=yy;
            }
        }
    }
    if(K<=tim || cnt[tim+1]==0)printf("%d\n",r);
    else {
        long long p=K-tim,u=p,v=p+1;
        if(u%2==0)u/=2; else v/=2;
        printf("%d\n",(u%mo*(v%mo)%mo*28%mo+p%mo*cnt[tim+1]%mo+r)%mo);
    }
    }
    return 0;
}