题目描述

非負整数 $K$ に対し、以下のようにレベル $K$ のフラクタルを定義します。

• レベル $0$ のフラクタルとは、白いマス一個のみからなるグリッドである。
• $K\ >\ 0$ のとき、レベル $K$ のフラクタルは $3^K\ \times\ 3^K$ のグリッドである。このグリッドを $3^{K-1}\ \times\ 3^{K-1}$ のブロック $9$ 個に分割したとき、
  • 中央のブロックは全て黒マスからなる。
  • 他の $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$ $:$ $a_Q\ b_Q\ c_Q\ d_Q$

输出格式

$Q$ 行出力せよ。 $i$ 行目には、$(a_i,\ b_i)$ から $(c_i,\ d_i)$ への距離を出力せよ。

题目大意

定义

$k$ 级图表示长宽均为 $3^k$ 的图,将图分为9部分(见题目,每部分边长为 $3^{k-1}$ ),最中间一部分全为黑,剩下的每一部分都是一个 $k-1$ 级图.

现有 $\infty$ 级图，格点为黑的表示不能走，询问 $Q$ 次 $(a_i,b_i)$ 到 $(c_i,d_i)$ 的最短距离。不能走斜线.

数据范围

$1 \leq Q \leq 10000$

$1 \leq ai,bi,ci,di \leq 3^{30}$

保证 询问的两点不会是同一位置,所有输入都是整数.

样例解释

2
4 2 7 4
9 9 1 9

5
8

提示

制約

• $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)$ は白マスである。
• 入力は全て整数である。

Sample Explanation 1