310295: CF1811B. Conveyor Belts

B. Conveyor Beltstime limit per test3 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

Conveyor matrix $m_n$ is matrix of size $n \times n$, where $n$ is an even number. The matrix consists of concentric ribbons moving clockwise.

In other words, the conveyor matrix for $n = 2$ is simply a matrix $2 \times 2$, whose cells form a cycle of length $4$ clockwise. For any natural $k \ge 2$, the matrix $m_{2k}$ is obtained by adding to the matrix $m_{2k - 2}$ an outer layer forming a clockwise cycle.

The conveyor matrix $8 \times 8$.

You are standing in a cell with coordinates $x_1, y_1$ and you want to get into a cell with coordinates $x_2, y_2$. A cell has coordinates $x, y$ if it is located at the intersection of the $x$th row and the $y$th column.

Standing on some cell, every second you will move to the cell next in the direction of movement of the tape on which you are. You can also move to a neighboring cell by spending one unit of energy. Movements happen instantly and you can make an unlimited number of them at any time.

Your task is to find the minimum amount of energy that will have to be spent to get from the cell with coordinates $x_1, y_1$ to the cell with coordinates $x_2, y_2$.

For example, $n=8$ initially you are in a cell with coordinates $1,3$ and you want to get into a cell with coordinates $6, 4$. You can immediately make $2$ movements, once you are in a cell with coordinates $3, 3$, and then after $8$ seconds you will be in the right cell.

Input

The first line contains an integer $t$ ($1 \le t \le 2 \cdot 10^5$) — the number of test cases.

The descriptions of the test cases follow.

The description of each test case consists of one string containing five integers $n$, $x_1$, $y_1$, $x_2$ and $y_2$ ($1 \le x_1, y_1, x_2, y_2 \le n \le 10^9$) — matrix size and the coordinates of the start and end cells. It is guaranteed that the number $n$ is even.

Output

For each test case, print one integer in a separate line — the minimum amount of energy that will have to be spent to get from the cell with coordinates $x_1, y_1$ to the cell with coordinates $x_2, y_2$.

ExampleInput

5
2 1 1 2 2
4 1 4 3 3
8 1 3 4 6
100 10 20 50 100
1000000000 123456789 987654321 998244353 500000004

Output

0
1
2
9
10590032

题目大意：
传送带矩阵 $ m_n $ 是一个 $ n \times n $ 大小的矩阵，其中 $ n $ 是一个偶数。这个矩阵由按顺时针方向移动的同心带组成。

换句话说，对于 $ n = 2 $，传送带矩阵就是一个简单的 $ 2 \times 2 $ 矩阵，其单元格形成一个长度为 4 的顺时针循环。对于任何自然数 $ k \ge 2 $，矩阵 $ m_{2k} $ 是通过在矩阵 $ m_{2k - 2} $ 的外部添加一个形成顺时针循环的外层得到的。

你站在坐标为 $ x_1, y_1 $ 的单元格中，你想进入坐标为 $ x_2, y_2 $ 的单元格。一个单元格的坐标是 $ x, y $，如果它位于第 $ x $ 行和第 $ y $ 列的交点上。

站在某个单元格上，每秒钟你会移动到带子上移动方向的下一个单元格。你也可以花费一个单位的能量移动到相邻的单元格。移动是瞬时的，你可以在任何时间进行无限次的移动。

你的任务是找到从坐标为 $ x_1, y_1 $ 的单元格到坐标为 $ x_2, y_2 $ 的单元格所需花费的最小能量量。

输入输出数据格式：
输入：
- 第一行包含一个整数 $ t $ ($ 1 \le t \le 2 \cdot 10^5 $) —— 测试用例的数量。
- 接下来是 $ t $ 个测试用例的描述，每个测试用例包含一行，有五个整数 $ n $, $ x_1 $, $ y_1 $, $ x_2 $, $ y_2 $ ($ 1 \le x_1, y_1, x_2, y_2 \le n \le 10^9 $) —— 矩阵大小和起始和结束单元格的坐标。保证 $ n $ 是一个偶数。

输出：
- 对于每个测试用例，打印一行，包含一个整数 —— 从坐标为 $ x_1, y_1 $ 的单元格到坐标为 $ x_2, y_2 $ 的单元格所需花费的最小能量量。题目大意： 传送带矩阵 $ m_n $ 是一个 $ n \times n $ 大小的矩阵，其中 $ n $ 是一个偶数。这个矩阵由按顺时针方向移动的同心带组成。 换句话说，对于 $ n = 2 $，传送带矩阵就是一个简单的 $ 2 \times 2 $ 矩阵，其单元格形成一个长度为 4 的顺时针循环。对于任何自然数 $ k \ge 2 $，矩阵 $ m_{2k} $ 是通过在矩阵 $ m_{2k - 2} $ 的外部添加一个形成顺时针循环的外层得到的。 你站在坐标为 $ x_1, y_1 $ 的单元格中，你想进入坐标为 $ x_2, y_2 $ 的单元格。一个单元格的坐标是 $ x, y $，如果它位于第 $ x $ 行和第 $ y $ 列的交点上。 站在某个单元格上，每秒钟你会移动到带子上移动方向的下一个单元格。你也可以花费一个单位的能量移动到相邻的单元格。移动是瞬时的，你可以在任何时间进行无限次的移动。 你的任务是找到从坐标为 $ x_1, y_1 $ 的单元格到坐标为 $ x_2, y_2 $ 的单元格所需花费的最小能量量。 输入输出数据格式： 输入： - 第一行包含一个整数 $ t $ ($ 1 \le t \le 2 \cdot 10^5 $) —— 测试用例的数量。 - 接下来是 $ t $ 个测试用例的描述，每个测试用例包含一行，有五个整数 $ n $, $ x_1 $, $ y_1 $, $ x_2 $, $ y_2 $ ($ 1 \le x_1, y_1, x_2, y_2 \le n \le 10^9 $) —— 矩阵大小和起始和结束单元格的坐标。保证 $ n $ 是一个偶数。 输出： - 对于每个测试用例，打印一行，包含一个整数 —— 从坐标为 $ x_1, y_1 $ 的单元格到坐标为 $ x_2, y_2 $ 的单元格所需花费的最小能量量。