#include <bits/stdc++.h>

using namespace std;

const int M = 5000 + 7;

int odl[M][M];

const int INF = 1e9 + 7;

int X[8] = {1,0,-1,0,1,-1,1,-1};
int Y[8] = {0,1,0,-1,1,-1,-1,1};

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	int N , q;
	
	cin >> N >> q;
	
	memset(odl,INF,sizeof odl);
	
	queue<pair<int,int> > Q;
	
	for(int i = 0 ; i < N;i++)
	{
		int x , y;
		cin >> x >> y;
		odl[x][y] = 0;
		Q.push({x,y});
	}
	
	while((int)Q.size())
	{
		int x = Q.front().first;
		int y = Q.front().second;
		Q.pop();
		for(int id = 0 ; id < 8 ; id++)
		{
			int nx = x + X[id];
			int ny = y + Y[id];
			
			if(nx >= 0 && nx < M && ny >= 0 && ny < M)
			{
				if(odl[nx][ny] > odl[x][y] + 1)
				{
					odl[nx][ny] = odl[x][y] + 1;
					Q.push({nx,ny});
				}
			}
		}
	}
	
	while(q--)
	{
		int a , b;
		cin >> a >> b;
		cout << odl[a][b] << "\n";
	}
	
	return 0;
}