#include<cstdio>
#include<cctype>
#include<queue>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
#define rep(i,a,b) for(int i=a;i<b;++i)
#define per(i,a,b) for(int i=b-1;i>=a;--i)
#define set(a,b) memset(a,b,sizeof(a))
#define de(x) cout << #x << " = " << x << endl
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define fi first
#define se second
typedef long long ll;
typedef double db;
typedef pair<int, int> pii;
typedef vector<int> vi;
const double pi = acos(-1.0), eps = 1e-8;
const int inf = ~0U >> 2;
int mod = 1e9 + 7;
int Pow(int x,ll t){int r=1;for(;t;t>>=1,x=(ll)x*x%mod)if(t&1)r=(ll)r*x%mod;return r;}
const int N = 200 , M = 200 , limit = 50 , P = 1e9 + 7;
const int dx[] = {2 , 2 , 1 , 1 , -1, -1 , -2 , -2};
const int dy[] = {1 , -1 , 2, -2, 2 , -2 , 1 , -1};
int dis[N*2][M*2] , cnt[N];
ll K,n;

int main(){
    int T;cin>>T;
    while(T--) {
    cin >> K >> n;
    int x , y;
    memset(dis,0,sizeof(dis));
    memset(cnt,0,sizeof(cnt));
    rep(i,0,n) cin >> x >> y , dis[N + x][M + y] = inf;
    dis[N][M] = 1;
    vector<pii> V;V.pb(mp(N , M));
    rep(i,0,sz(V)){
        pii c = V[i];
        int x = c.fi , y = c.se;
        if(dis[x][y] == K + 1 || dis[x][y] == limit + 1) break;
        rep(d,0,8){
            int nx = x + dx[d] , ny = y + dy[d];
            if(!dis[nx][ny]){
                dis[nx][ny] = dis[x][y] + 1;
                cnt[dis[nx][ny]]++;
                V.pb(mp(nx , ny));
            }
        }
    }
    if(K <= limit || cnt[limit+1] == 0) cout << sz(V) << endl;
    else{
        ll d = K - limit , a = d , b = d+1;
        if(a&1) b>>=1 ; else a>>=1;
        cout << ((a%P) * (b%P)%P * 28 % P + d % P * cnt[limit+1] % P + sz(V))%P << endl;
    }
}
    return 0;
}