← 返回题目列表

Codeforces · 1811/B

B. 传送带

中文机器翻译题面 查看原题

传送矩阵 $$$m_n$$$ 是大小为 $$$n \times n$$$ 的矩阵,其中 $$$n$$$ 是偶数。该矩阵由顺时针移动的同心丝带组成。

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

输送机矩阵 $$$8 \times 8$$$。

您正站在坐标为 $$$x_1, y_1$$$ 的单元格中,并且想要进入坐标为 $$$x_2, y_2$$$ 的单元格。如果单元格位于第 $$$x$$$ 行和第 $$$y$$$ 列的交叉点,则该单元格的坐标为 $$$x, y$$$。

站在某个单元格上,每秒您都会按照您所在磁带的移动方向移动到下一个单元格。您还可以通过消耗一个单位的能量来移动到相邻的单元格。动作立即发生,您可以随时进行无限数量的动作。

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

例如,$$$n=8$$$ 最初您位于坐标为 $$$1,3$$$ 的单元格中,并且您想要进入坐标为 $$$6, 4$$$ 的单元格。一旦您进入坐标为 $$$3, 3$$$ 的单元格,您就可以立即进行 $$$2$$$ 移动,然后在 $$$8$$$ 秒后您将进入正确的单元格。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 2 \cdot 10^5$$$) — 测试用例的数量。

测试用例的描述如下。

每个测试用例的描述由一个字符串组成,其中包含五个整数 $$$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$$$ 的单元格所需花费的最小能量。

示例

输入 #1

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

输出 #1

0
1
2
9
10590032