马的遍历

题目描述

有一个 $n \times n$ 的棋盘(棋盘边界是$[1, n]$)，在某个点 $(x1, y1)$ 上有一个马，要求你计算出马到达棋盘上另一个点 $(x2, y2)$最少要走几步。

输入格式

输入第一行两个整数，分别为 $n, t$, ,表示棋盘大小和询问次数。

之后$t$行, 每一行有四个整数$x1, y1, x2, y2$, 表示询问从$(x1, y1)$ 到 $(x2, y2)$至少需要多少步

输出格式

输出 $t$ 行，每行一个整数代表最少要走几步。

样例 #1

样例输入 #1

8 4
7 1 3 6
6 2 4 8
8 6 6 5
5 2 4 5

样例输出 #1

3
4
1
2

提示

数据规模与约定

对于全部的测试点，保证 $4 \leq n \leq 1000$，$1 \leq t \leq 1000$。

保证所有的起点终点均在棋盘上