#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(i, a, n) for (int i = (a); i < (n); i++)
#define per(i, a, n) for (int i = (n) - 1; i >= (a); i--)
#define fi first
#define se second
int n,q;
int a[5001][5001];
bool flag[5001][5001];
int main(void)
{
    scanf("%i %i", &n, &q);
    //printf("a");
    queue<pair<int,int> > f;
    int i;
    for(i=0;i<n;i++){
        int b,c;
        scanf("%i %i", &b, &c);
        if(flag[b][c]==false) f.push({b,c});
        flag[b][c]=true;
    }
    vector<pair<int,int>> p={{-1,-1},{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1}};
    while(!f.empty()){
        //printf("a");
        auto x=f.front();
        f.pop();
        for(i=0;i<8;i++){
            auto y=x;
            y.fi+=p[i].fi;
            y.se+=p[i].se;
            if(y.fi>=0&&y.fi<=5000&&y.se>=0&&y.se<=5000){
                if(flag[y.fi][y.se]) continue;
                flag[y.fi][y.se]=true;
                a[y.fi][y.se]=a[x.fi][x.se]+1;
                f.push(y);
            }
        }
    }
    //printf("b");
    for(i=0;i<q;i++){
        //printf("c");
        int b,c;
        scanf("%i %i", &b, &c);
        printf("%i\n",a[b][c]);
    }
    return 0;
}