import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Queue;

/**
 *
 * @author tym3
 */
public class Security {
    static int[][] D = {
        {-1, +1},
        { 0, +1},
        {+1, +1},
        {-1,  0},
        {+1,  0},
        {-1, -1},
        { 0, -1},
        {+1, -1},
    };
    
    static class P {
        int x, y;
        P(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] f = br.readLine().split(" ");
        int nGuards = Integer.parseInt(f[0]);
        int nIncidents = Integer.parseInt(f[1]);
        
        List<P> guards = new ArrayList<>(nGuards);
        for (int i = 0; i < nGuards; ++i) {
            f = br.readLine().split(" ");
            guards.add(new P(Integer.parseInt(f[0]), Integer.parseInt(f[1])));
        }
        
        List<P> incidents = new ArrayList<>(nIncidents);
        for (int i = 0; i < nIncidents; ++i) {
            f = br.readLine().split(" ");
            incidents.add(new P(Integer.parseInt(f[0]), Integer.parseInt(f[1])));
        }
        
        short[][] df = new short[5001][5001];
        for (short[] row: df) {
            Arrays.fill(row, Short.MAX_VALUE);
        }
        
        List<P> guards2 = new ArrayList<>(nGuards);
        for (P g: guards) {
            if (df[g.x][g.y] != 0) {
                df[g.x][g.y] = 0;
                guards2.add(g);
            }
        }
        guards = guards2; // without duplicities
        
        
        Queue<P> q = new ArrayDeque<>();
        q.addAll(guards2);
        
        while (!q.isEmpty()) {
            P p = q.remove();
            
            for (int[] d: D) {
                int x2 = p.x + d[0];
                int y2 = p.y + d[1];
                if (x2 >= 0 && y2 >= 0 && x2 <= 5000 && y2 <= 5000 && df[x2][y2] == Short.MAX_VALUE) { // can visit neighbor
                    q.add(new P(x2, y2));
                    df[x2][y2] = (short)(df[p.x][p.y] + 1);
                }
            }
        }
        
        PrintWriter pw = new PrintWriter(System.out);
        for (P inc: incidents) {
            pw.println(df[inc.x][inc.y]);
        }
        pw.flush();
    }
    
}