#include <bits/stdc++.h>

using namespace std;

typedef long long int ll;
typedef double ld;

typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;

#define PB push_back
#define ff first
#define ss second

#define FOR(prom,a,b) for ( ll prom = (a); prom < (ll)(b); ++prom)
#define F(a) FOR(i,0,a)
#define FF(a) FOR(j,0,a)

//#define M_PI 3.14159265358979323846
#define EPS (1e-10)
#define EQ(a,b) (fabs(a-b) <= fabs(a+b)*EPS)
#define LINF (1<<62LL)
#define DEB cerr<<"DEB: "

#define MX 0
int pom[]={-1,0,1};

struct Node{
	int first,second,num;
	Node(int a,int b,int c):first(a),second(b),num(c){}
};

int main() {
	int N,Q;
	scanf(" %d %d",&N,&Q);
	vector <vi> arr(5001,vi(5001,-1));	
	queue<Node> que;
	F(N){
		int x,y;
		scanf(" %d %d",&x,&y);
		FOR(k,0,3)
			FF(3)
				if (k!=1||j!=1){
					Node po(x+pom[k],y+pom[j],1);			
					que.push(po);
				}
		arr[x][y]=0;
	}
	while(!que.empty()){
		Node now=que.front();
		que.pop();
		if( arr[now.ff][now.ss]!=-1||now.ff<0||now.ff>5000||now.ss<0||now.ff>5000)continue;
		arr[now.ff][now.ss]=now.num;
		FOR(k,0,3)
			FF(3)
				if (k!=1||j!=1){
					Node po(now.ff+pom[k],now.ss+pom[j],now.num+1);			
					que.push(po);
				}
	}
	F(Q){
		int x,y;
		scanf(" %d %d",&x,&y);
		printf("%d\n",arr[x][y]);
	}
	return 0;

}