← 返回题目列表

AtCoder · panasonic2020_f

F. 分形最短路径

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

分数: 600 点

问题陈述

对于非负整数 K,我们定义水平分形 K 如下:

  • 水平分形 0 是一个只有一个白色方块的网格。
  • 当 K > 0,水平分形 K 是 3^K \times 3^K 网格。如果我们把这个网格分成九个 3^{K-1} \times 3^{K-1} 子网格:
    • 中央子网格仅由黑色方块组成。
    • 其他八个子网格都是水平分形 K-1.

例如,水平分形 2 如下:

A fractal of level 2

在水平分形中 30,让 (r, c) 表示 r从顶部开始的第行和 c左起第 列。

你被给予 Q 整数的四元组 (a_i, b_i, c_i, d_i)。 对于每个四元组,求距离 (a_i, b_i) to (c_i, d_i).

这里距离 (a, b) to (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}) 分享一面。

约束

  • 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) 是白色方块。
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

Q
a_1 \ b_1 \ c_1 \ d_1
:
a_Q \ b_Q \ c_Q \ d_Q

输出

打印 Q 行。 的 i第行应包含距 (a_i, b_i) to (c_i, d_i).


示例输入 1

2
4 2 7 4
9 9 1 9

示例输出 1

5
8