AT_panasonic2020_f Fractal Shortest Path

对于非负整数 $K$，定义如下的 $K$ 级分形图案。 - $0$ 级分形是仅包含一个白色格子的网格。 - 当 $K > 0$ 时，$K$ 级分形是一个 $3^K \times 3^K$ 的网格。将该网格划分为 $9$ 个 $3^{K-1} \times 3^{K-1}$ 的子块时， - 中央的子块全部为黑色格子。 - 其余 $8$ 个子块均为 $K-1$ 级分形。 例如，$2$ 级分形如下图所示。  在 $30$ 级分形中，将从上往下第 $r$ 行，从左往右第 $c$ 列的格子记作 $(r, c)$。 给定 $Q$ 组整数 $(a_i, b_i, c_i, d_i)$，对于每组，求从 $(a_i, b_i)$ 到 $(c_i, d_i)$ 的距离。 这里，从 $(a, b)$ 到 $(c, d)$ 的距离定义为满足以下条件的最小 $n$： - 存在一条仅经过白色格子的路径 $(x_0, y_0), \ldots, (x_n, y_n)$，满足： - $(x_0, y_0) = (a, b)$ - $(x_n, y_n) = (c, d)$ - 对于任意 $i$（$0 \leq i \leq n-1$），格子 $(x_i, y_i)$ 与 $(x_{i+1}, y_{i+1})$ 边相邻。

输入从标准输入读入，格式如下： > $Q$ > $a_1\ b_1\ c_1\ d_1$ > $\vdots$ > $a_Q\ b_Q\ c_Q\ d_Q$

输出共 $Q$ 行。第 $i$ 行输出从 $(a_i, b_i)$ 到 $(c_i, d_i)$ 的距离。

### 数据范围 - $1 \leq Q \leq 10000$ - $1 \leq a_i, b_i, c_i, d_i \leq 3^{30}$ - $(a_i, b_i) \neq (c_i, d_i)$ - $(a_i, b_i)$ 和 $(c_i, d_i)$ 均为白色格子 - 输入均为整数 ### 样例解释 1  由 ChatGPT 4.1 翻译