#include <bits/stdc++.h>
using namespace std;

  char grid[5003][5003];
  int dist[5003][5003];

int main(){
  int N, Q, x, y;
  cin >> N >> Q;

  for(int i = 0; i<5003; i++){
    for(int j = 0; j<5003; j++){
      grid[i][j] = '.';
      dist[i][j] = 0;
    }
  }

  for(int i = 0; i< 5003; i++){
    grid[0][i] = '#';
    grid[i][0] = '#';
    grid[5002][i] = '#';
    grid[i][5002] = '#';
  }

  queue<pair<int, int> > q;
  for(int i = 0; i<N; i++){
    cin >> x >> y;
    q.push(make_pair(x + 1, y + 1));
    grid[x + 1][y + 1] = '/';
  }

  while(!q.empty()){
    x = q.front().first;
    y = q.front().second;
    q.pop();

    if(grid[x + 1][y + 1] == '.'){
      grid[x + 1][y + 1] = '#';
      dist[x + 1][y + 1] = dist[x][y] + 1;
      q.push(make_pair(x + 1, y + 1));
    }

    if(grid[x + 1][y] == '.'){
      grid[x + 1][y] = '#';
      dist[x + 1][y] = dist[x][y] + 1;
      q.push(make_pair(x + 1, y));
    }

    if(grid[x][y + 1] == '.'){
      grid[x][y + 1] = '#';
      dist[x][y + 1] = dist[x][y] + 1;
      q.push(make_pair(x, y + 1));
    }

    if(grid[x + 1][y - 1] == '.'){
      grid[x + 1][y - 1] = '#';
      dist[x + 1][y - 1] = dist[x][y] + 1;
      q.push(make_pair(x + 1, y - 1));
    }

    if(grid[x - 1][y + 1] == '.'){
      grid[x - 1][y + 1] = '#';
      dist[x - 1][y + 1] = dist[x][y] + 1;
      q.push(make_pair(x - 1, y + 1));
    }

    if(grid[x][y - 1] == '.'){
      grid[x][y - 1] = '#';
      dist[x][y - 1] = dist[x][y] + 1;
      q.push(make_pair(x, y - 1));
    }

    if(grid[x - 1][y] == '.'){
      grid[x - 1][y] = '#';
      dist[x - 1][y] = dist[x][y] + 1;
      q.push(make_pair(x - 1, y));
    }

    if(grid[x - 1][y - 1] == '.'){
      grid[x - 1][y - 1] = '#';
      dist[x - 1][y - 1] = dist[x][y] + 1;
      q.push(make_pair(x - 1, y - 1));
    }
  }

  for(int i = 0; i<Q; i++){
    cin >> x >> y;
    cout << dist[x + 1][y + 1] << endl;
  }
}