/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */

/* 
 * File:   main.cpp
 * Author: cteam014
 *
 * Created on October 20, 2018, 10:48 AM
 */

#include <map>
#include <list>
#include <queue>
#include <iostream>
#include <set>

using namespace std;


int main(int argc, char** argv) {
    int guardsNum, incidentsNum;
    cin >> guardsNum;
    cin >> incidentsNum;
    
    map<pair<int,int>,bool> guards;
    
    int x,y;
    for (int i = 0; i<guardsNum; ++i){
        cin >> x;
        cin >> y;
        
        guards[make_pair(x,y)] = true;
    }
    
    for (int i = 0; i<incidentsNum; ++i){
        cin >> x;
        cin >> y;
        
        set<pair<int,int>> visited;
        int level = 0;
        
        queue<pair<int,int>> q;
        q.push(make_pair(x,y));
        q.push(make_pair(-1,-1));
        
        while(!q.empty()){
            pair<int,int> p = q.front();
            //cout << p.first << " " << p.second<<endl;
            q.pop();
            
            if (p.first == -1){
                if (q.back().first == -1)
                    break;
                
                level++;
                q.push(make_pair(-1,-1));
                continue;
            }
            
            if (visited.count(p) > 0)
                continue;
            
            if (guards.count(p) > 0){
                cout << level << endl;
                break;
            }
            
            if (p.first +1 < 5000){
                if (p.second +1 < 5000)
                  q.push(make_pair(p.first +1,p.second +1));
                if (p.second -1 >=0)
                  q.push(make_pair(p.first +1,p.second -1));
                
                q.push(make_pair(p.first +1,p.second));
            }
            if (p.first -1 > 0){
                if (p.second +1 < 5000)
                  q.push(make_pair(p.first -1,p.second +1));
                if (p.second -1 >=0)
                  q.push(make_pair(p.first -1,p.second -1));
                
                q.push(make_pair(p.first -1,p.second));
            }
            
            if (p.second -1 >=0)
                  q.push(make_pair(p.first,p.second -1));
            
            if (p.second +1 < 5000)
                  q.push(make_pair(p.first,p.second +1));
        }
    }
    
    return 0;
}