Problem:
 Score : 600 points    Problem Statement For a non-negative integer K , we define a fractal of level K as follows:   A fractal of level 0 is a grid with just one white square.  When K > 0 , a fractal of level K is a 3^K \times 3^K grid. If we divide this grid into nine 3^{K-1} \times 3^{K-1} subgrids:  The central subgrid consists of only black squares.  Each of the other eight subgrids is a fractal of level K-1 .     For example, a fractal of level 2 is as follows:   In a fractal of level 30 , let (r, c) denote the square at the r -th row from the top and the c -th column from the left.  You are given Q quadruples of integers (a_i, b_i, c_i, d_i) .
For each quadruple, find the distance from (a_i, b_i) to (c_i, d_i) .  Here the distance from (a, b) to (c, d) is the minimum integer n that satisfies the following condition:   There exists a sequence of white squares (x_0, y_0), \ldots, (x_n, y_n) satisfying the following conditions:  (x_0, y_0) = (a, b)  (x_n, y_n) = (c, d)  For every i (0 \leq i \leq n-1) , (x_i, y_i) and (x_{i+1}, y_{i+1}) share a side.         Constraints  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) and (c_i, d_i) are white squares.  All values in input are integers.         Input Input is given from Standard Input in the following format:  Q  a_1 \ b_1 \ c_1 \ d_1  :  a_Q \ b_Q \ c_Q \ d_Q       Output Print Q lines.
The i -th line should contain the distance from (a_i, b_i) to (c_i, d_i) .        Sample Input 1 2
4 2 7 4
9 9 1 9      Sample Output 1 5
8

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


q = int(input())
def _sub(a):
    v = []
    for i in range(35):
        a,val = divmod(a,3)
        v.append(val)
    return v
def sub(a,b,c,d):
    va,vb,vc,vd = _sub(a), _sub(b), _sub(c), _sub(d)
    ans = 0
    m1 = True
    m2 = True
    for i in reversed(range(35)):
        aa,bb,cc,dd = va[i],vb[i],vc[i],vd[i]
        if aa==cc==1 and m1 and ((m2 and bb!=dd) or (not m2 and abs(b-d)>2*pow(3,i))):

            ta = a % pow(3,i)
            tc = c % pow(3,i)
            ans = abs(b-d) + min(ta+tc+2, 2*pow(3,i)-(ta+tc))
            break
        elif bb==dd==1 and m2 and ((m1 and aa!=cc) or (not m1 and abs(a-c)>2*pow(3,i))):

            tb = b % pow(3,i)
            td = d % pow(3,i)
            ans = abs(a-c) + min(tb+td+2, 2*pow(3,i)-(tb+td))
            break
        else:
            if aa!=cc:
                m1 = False
            if bb!=dd:
                m2 = False
    else:
        ans = abs(a-c) + abs(b-d)
    return ans
ans = [None]*q
for i in range(q):
    a,b,c,d = list(map(lambda x: int(x)-1, input().split()))
    ans[i] = sub(a,b,c,d)
write("\n".join(map(str, ans)))

Solution (Python):

import math
Q = int(input())
A = [list(map(int, input().split())) for _ in range(Q)]



def measure(A):
    a,b,c,d = A
    if abs(a-c) < abs(b-d):
        s1, s2 = min([a,c]), max([a,c])
        l1, l2 = min([b,d]), max([b,d])
    else:
        l1, l2 = min([a,c]), max([a,c])
        s1, s2 = min([b,d]), max([b,d])
    min_K = int(math.log(s2-s1+1, 3) + 1)
    max_K = int(math.log(l2-l1+1, 3) + 1)
    for k in list(range(min_K, max_K+1))[::-1]:
        v = 3 ** k
        _l = 3 ** (k-1) + 1
        _h = (3 ** (k-1)) * 2
        c1 = s1//v == s2//v
        c2 = (s1 % v <= _h) & (_l <= s1 % v)
        c3 = (s2 % v <= _h) & (_l <= s2 % v)
        c4 = True
        if (l1 // v) == (l2  // v):
            if (l1 % v < _l) & (l2 % v > _h):
                c4 = True
            else:c4=False
        if ((l1 // v) + 1) == (l2 // v):
            if ((l2 % v < _l) & (l1 % v > _h)):
                c4 = False
        if c1 & c2 & c3 & c4:
            val1 = (s1 % v - _l + 1) + (s2 % v - _l + 1) + (l2 - l1)
            val2 = (_h - s1 % v + 1) + (_h - s2 % v + 1) + (l2 - l1)
            print(min([val1, val2]))
            return None
    print(l2-l1+s2-s1)

if __name__ == '__main__':
    for val in A:
        measure(val)

Solution (Python):
Q=int(input())
Query=[tuple(map(int,input().split())) for i in range(Q)]

B=[(3,2)]
for i in range(2,31):
    B.append((3**i,B[-1][1]+3**(i-1)))

for a,b,c,d in Query:
    MINX=min(a,c)
    MAXX=max(a,c)
    MINY=min(b,d)
    MAXY=max(b,d)
    flag=0
    
    for i in range(29,-1,-1):
        r,q=B[i]
        l=3**i

        xcen=-(-(MINX-q)//r)*r+q
        ycen=-(-(MINY-q)//r)*r+q

        for xq in [xcen-r,xcen,xcen+r]:
            for yq in [ycen-r,ycen,ycen+r]:

                

                if (MINX<xq-l//2 and xq+l//2<MAXX) and (yq-l//2<=MINY and MAXY<=yq+l//2):
                    
                    flag=1
                    break
                
                if (xq-l//2<=MINX and MAXX<=xq+l//2) and (MINY<yq-l//2 and yq+l//2<MAXY):
                    
                    flag=2
                    break
            if flag!=0:
                break
        if flag!=0:
            break

    if flag==0:
        print(MAXX-MINX+MAXY-MINY)

    elif flag==1:
        ANS=MAXX-MINX
        y1=yq+l//2+1
        y2=yq-l//2-1

        ANS+=min(abs(y1-b)+abs(y1-d),abs(y2-b)+abs(y2-d))

        print(ANS)

    else:
        ANS=MAXY-MINY
        x1=xq+l//2+1
        x2=xq-l//2-1

        ANS+=min(abs(x1-a)+abs(x1-c),abs(x2-a)+abs(x2-c))

        print(ANS)

Solution (Python):
def solve(A,B,C,D, level):
    E = 3**level
    if level == -1:
        return int(abs(A-C) + abs(B-D))
    a,b,c,d = A//E, B//E, C//E, D//E
    if a != c and b != d:
        return int(abs(A-C) + abs(B-D))

    if a == c and b==d:
        return solve(A,B,C,D,level-1)

    if a != c and b==d:
        A,B,C,D = B,A,D,C
        a,b,c,d = b,a,d,c

    if b != d and a == c:
        if a%3 != 1:
            return solve(A,B,C,D,level-1)
        if abs(b-d) == 1:
            return solve(A,B,C,D,level-1)

        if B > D:
            A, B, C, D = C, D, A, B
            a, b, c, d = c, d, a, b

        x = E * a -1
        y1 = E * (b+1) -1
        y2 = E * d
        d = abs(x-A) + abs(y1-B) + abs(y1-y2) + abs(x-C) + abs(y2-D)
        x = E *(a+1)
        d2 = abs(x-A) + abs(y1-B) + abs(y1-y2) + abs(x-C) + abs(y2-D)
        return min(d,d2)

N = int(input())

for i in range(N):
    sg = [int(j.strip())  for j in input().split(' ')]
    s,g = [sg[0]-1,sg[1]-1],[sg[2]-1,sg[3]-1]
    A,B,C,D = s[0],s[1],g[0],g[1]
    print(solve(A,B,C,D,30))

Solution (Python):
def solve(a, b, c, d):
  a, c = sorted([a, c])
  b, d = sorted([b, d])
  for k in range(30, 0, -1):
    block_size = 3**k
    box_size = block_size // 3
    x1, y1, x2, y2 = map(lambda x:x//box_size, (a, b, c, d))
    if x1 != x2 and y1 != y2:
      return c-a + d-b
    elif x1 == x2 and x1%3 == 1 and (y1+1)//3*3+1 < y2:
      shifted = (a+c) % (2*block_size)
      return min(shifted-2*box_size+2, 4*box_size-shifted) + d-b
    elif y1 == y2 and y1%3 == 1 and (x1+1)//3*3+1 < x2:
      shifted = (b+d) % (2*block_size)
      return min(shifted-2*box_size+2, 4*box_size-shifted) + c-a
  return c-a + d-b

for i in range(int(input())):
  print(solve(*map(lambda x:int(x)-1, input().split())))

Solution (Python):
def solve(a, b, c, d):
  for k in range(29, -1, -1):
    block_size = 3**k
    box_size = block_size * 3
    x1, y1, x2, y2 = map(lambda x:x//block_size, (a, b, c, d))
    x1, x2 = sorted([x1, x2])
    y1, y2 = sorted([y1, y2])
    if x1!=x2 and y1!=y2:
      return abs(a-c)+abs(b-d)
    if x1==x2 and x1%3==1 and (y1+1)//3*3+1<y2:
      a, c = map(lambda x:x%box_size, (a, c))
      return min(a+c-2*block_size+2, 4*block_size-a-c)+abs(b-d)
    elif y1==y2 and y1%3==1 and (x1+1)//3*3+1<x2:
      b, d = map(lambda x:x%box_size, (b, d))
      return min(b+d-2*block_size+2, 4*block_size-b-d)+abs(a-c)
  return abs(a-c)+abs(b-d)

for i in range(int(input())):
  print(solve(*map(lambda x:int(x)-1, input().split())))

Solution (Python):
import itertools
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7





def get_block(X1, Y1, X2, Y2):
    
    if X1 > X2:
        X1, X2 = X2, X1
    if Y1 > Y2:
        Y1, Y2 = Y2, Y1
    size = pow(3, 30)
    for level in reversed(range(31)):
        x1 = X1 // size
        x2 = X2 // size
        y1 = Y1 // size
        y2 = Y2 // size
        if y1 == y2 and y1 % 3 == y2 % 3 == 1:
            
            if x2 - x1 >= 2:
                while x1 % 3 != 1:
                    x1 += 1
                return x1 * size, y1 * size, size
        if x1 == x2 and x1 % 3 == x2 % 3 == 1:
            if y2 - y1 >= 2:
                while y1 % 3 != 1:
                    y1 += 1
                return x1 * size, y1 * size, size
        size //= 3
    return None


def dist(x1, y1, x2, y2):
    return abs(x1 - x2) + abs(y1 - y2)


def solve(X1, Y1, X2, Y2):
    
    block = get_block(X1, Y1, X2, Y2)
    ret = INF
    if block:
        x, y, size = block
        for x, y in itertools.product((x - 1, x + size), (y - 1, y + size)):
            ret = min(ret, dist(X1, Y1, x, y) + dist(X2, Y2, x, y))
    else:
        ret = min(ret, dist(X1, Y1, X2, Y2))
    return ret


Q = int(sys.stdin.buffer.readline())
ABCD = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(Q)]
for a, b, c, d in ABCD:
    a -= 1
    b -= 1
    c -= 1
    d -= 1
    ans = solve(a, b, c, d)
    print(ans)

Solution (Python):
q=abs;s=lambda t,i:0--t//3**i;m=lambda a,b,c,d:max([i for i in range(30)if s(a,i)==s(c,i)and s(a,i)%3==2and 1<q(s(b,i)-s(d,i))]+[-1])+1
for _ in[0]*int(input()):
  a,b,c,d=map(int,input().split());h=m(a,b,c,d);w=m(b,a,d,c)
  if h==w==0:print(q(b-d)+q(a-c));continue
  if h<w:h,a,b,c,d=w,b,a,d,c
  i=3**h//3;x=2*i+1;g=a-(a-1)%(3*i)-1;a-=g;c-=g;print(q(b-d)+min(q(i-a)+q(i-c),q(x-a)+q(x-c)))

Solution (Python):
s=lambda t,i:0--t//3**i
for _ in range(int(input())):
  a,b,c,d=map(int,input().split());mx=max([i for i in range(30) if s(a,i)==s(c,i)and s(a,i)%3==2and abs(s(b,i)-s(d,i))>=2]+[-1])+1;my=max([i for i in range(30) if s(b,i)==s(d,i)and s(b,i)%3==2and abs(s(a,i)-s(c,i))>=2]+[-1])+1
  if mx==my==0:print(abs(b-d)+abs(a-c));continue
  if mx<my:mx,a,b,c,d=my,b,a,d,c
  mi=3**(mx-1);ma=2*mi+1;ac=(3*mi)*((0--a//(3*mi))-1);a-=ac;c-=ac;print(abs(b-d)+min(abs(mi-a)+abs(mi-c),abs(ma-a)+abs(ma-c)))

Solution (Python):
def solve(aa,bb,cc,dd):
  a,b,c,d=aa,bb,cc,dd
  mx=my=0
  for i in range(1,31):
    if a==c and a%3==2 and abs(b-d)>=2:mx=i
    if b==d and b%3==2 and abs(a-c)>=2:my=i
    a=0--a//3
    b=0--b//3
    c=0--c//3
    d=0--d//3
  a,b,c,d=aa,bb,cc,dd
  if mx==my==0:return abs(a-c)+abs(b-d)
  if mx<my:
    ans=abs(a-c)
    mi=3**(my-1)
    ma=2*3**(my-1)+1
    bd=(3**my)*((0--b//(3**my))-1)
    b-=bd
    d-=bd
    ans+=min(abs(mi-b)+abs(mi-d),abs(ma-b)+abs(ma-d))
    return ans
  if mx>my:
    ans=abs(b-d)
    mi=3**(mx-1)
    ma=2*3**(mx-1)+1
    ac=(3**mx)*((0--a//(3**mx))-1)
    a-=ac
    c-=ac
    ans+=min(abs(mi-a)+abs(mi-c),abs(ma-a)+abs(ma-c))
    return ans
  if mx==my==0:return abs(a-c)+abs(b-d)
  ans=1/0
q=int(input())
for _ in range(q):
  a,b,c,d=map(int,input().split())
  print(solve(a,b,c,d))

Solution (Python):

q = int(input())
query = [tuple(map(int, input().split())) for _ in range(q)]

def man(a, b, c, d):
    return abs(a - c) + abs(b - d)

def solve(a, b, c, d, i, carry):
    if (a, b) == (c, d):
        return carry
    if i == 29:
        if (a, c) == (1, 1) or (b, d) == (1, 1):
            return 4 + carry
        else:
            return man(a,b,c,d) + carry
    k = 3 ** (30 - 1 - i)
    ga = a // k
    gb = b // k
    gc = c // k
    gd = d // k
    if (ga, gb) == (gc, gd):
        a %= k
        b %= k
        c %= k
        d %= k
        return solve(a,b,c,d,i+1,carry)
    if ga != gc and gb != gd:
        return man(a,b,c,d) + carry
    if gb == gd:
        a,b,c,d = b,a,d,c
        ga = a // k
        gb = b // k
        gc = c // k
        gd = d // k
    if ga == 1:
        return carry + abs(b - d) + min(a+c - 2*(k-1), 4*k - a - c)
    if b > d:
        a,b,c,d = c,d,a,b
        ga = a // k
        gb = b // k
        gc = c // k
        gd = d // k
    
    a %= k
    c %= k
    kk = k // 3
    gga = a // kk
    ggb = b // kk
    ggc = c // kk
    ggd = d // kk
    if ggd - ggb == 1:
        if gga == ggc:
            return solve(a % kk, b % kk, c % kk, d % kk + kk, i+1, carry)
        else:
            return man(a,b,c,d) + carry
    else:
        nb = b % kk
        nd = d % kk + 2 * kk
        carry += (d - b) - (nd - nb)
        return solve(a,nb,c,nd,i+1,carry)

for a, b, c, d in query:
    print(solve(a-1,b-1,c-1,d-1,0,0))

Solution (Python):
import numpy as np
Q = int(input())
ans = []
for loop1 in range(Q):
    a, b, c, d = map(int,input().split())
    a, b, c, d = a-1, b-1, c-1, d-1
    a1, b1, c1, d1 = a, b, c, d
    A, B, C, D = [], [], [], []
    for loop2 in range(30):
        A.append(a1 % 3)
        B.append(b1 % 3)
        C.append(c1 % 3)
        D.append(d1 % 3)
        a1 //= 3
        b1 //= 3
        c1 //= 3
        d1 //= 3
        if a1 + b1 + c1 + d1 == 0:
            break
    k = len(A)
    A = np.array(A)
    B = np.array(B)
    C = np.array(C)
    D = np.array(D)
    if a > c:
        A = 2 - A
        a = 3 ** k - 1 - a
        C = 2 - C
        c = 3 ** k - 1 - c
    if b > d:
        B = 2 - B
        b = 3 ** k - 1 - b
        D = 2 - D
        d = 3 ** k - 1 - d
    R = [0, 0]
    end = False
    for i in range(1, k + 1):
        if end:
            break
        R[0] = R[0] * 3 + A[-i]
        R[1] = R[1] * 3 + B[-i]
        if A[-i] == C[-i] and B[-i] == D[-i]:
            if i == k:
                ans.append(0)
            continue
        if A[-i] != C[-i] and B[-i] != D[-i]:
            ans.append((c - a) + (d - b))
            break
        else:
            if B[-i] == D[-i]:
                a, b, c, d = b, a, d, c
                A, B, C, D = B[0:], A[0:], D[0:], C[0:]
                R = R[::-1]
            if A[-i] == 1:
                mid1 = R[0] * (3 ** (k - i)) - 1
                mid2 = (R[0] + 1) * (3 ** (k - i))
                route1 = (a - mid1) + (d - b) + (c - mid1)
                route2 = (mid2 - a) + (d - b) + (mid2 - c)
                ans.append(min(route1, route2))
                break
            else:
                if i == k:
                    ans.append(d - b)
                    break
                bt = B[-i]
                dt = D[-i]
                for j in range(i + 1, k + 1):
                    R[0] = R[0] * 3 + A[-j]
                    bt = bt * 3 + B[-j]
                    dt = dt * 3 + D[-j]
                    dis = dt - bt
                    if A[-j] != C[-j]:
                        ans.append((c - a) + (d - b))
                        end = True
                        break
                    else:
                        if A[-j] == 1:
                            if dis > 1:
                                mid1 = R[0] * (3 ** (k - j)) - 1
                                mid2 = (R[0] + 1) * (3 ** (k - j))
                                route1 = (a - mid1) + (d - b) + (c - mid1)
                                route2 = (mid2 - a) + (d - b) + (mid2 - c)
                                ans.append(min(route1, route2))
                                end = True
                                break
                            else:
                                if j == k:
                                    ans.append(d - b)
                                    end = True
                                continue
                        else:
                            if j == k:
                                ans.append(d - b)
                                end = True
                            continue
for a in ans:
    print(a)

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI1(): return map(int1, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def solve(ai,aj,bi,bj):
    s=pow(3,30)
    dist=abs(ai-bi)+abs(aj-bj)
    while s>1:
        s//=3
        si,sj,ti,tj=ai//s,aj//s,bi//s,bj//s
        if si!=ti:
            return dist
        if abs(sj-tj)>1 and si%3==1:
            up=s*si-1
            down=s*(si+1)
            return min(min(ai,bi)-up,down-max(ai,bi))*2+dist
    return dist

def main():
    q=II()
    for _ in range(q):
        ai,aj,bi,bj=MI1()
        if abs(ai-bi)>abs(aj-bj):ai,aj,bi,bj=aj,ai,bj,bi
        print(solve(ai,aj,bi,bj))

main()

Solution (Python):
import sys
def grid(p, level):
    c = 3 ** level
    return ((p[0] % (3 * c)) // c, (p[1] % (3 * c)) // c)

def sub(p1, p2, level):
    
    if level < 0:
        return abs(p1[0] - p2[0]) + abs(p1[1] - p2[1])
    g1, g2 = grid(p1, level), grid(p2, level)
    assert 0 <= g1[0] < 3
    assert 0 <= g1[1] < 3
    assert 0 <= g2[0] < 3
    assert 0 <= g2[1] < 3
    if g1[0] != g2[0]:
        return abs(p1[0] - p2[0]) + abs(p1[1] - p2[1])
    if g1[0] == 1:
        c = 3 ** level
        y1, y2 = p1[1] // c, p2[1] //c
        if abs(y1 - y2) < 2:
            return sub(p1, p2, level - 1)
        i1, i2 = p1[0] % c, p2[0] % c
        xp = min(i1 + i2 + 2, 2 * c - i1 - i2)
        return xp + abs(p1[1] - p2[1])
    return sub(p1, p2, level - 1)

def solve(p1, p2, level):
    g1, g2 = grid(p1, level), grid(p2, level)
    if g1 == g2:
        if level == 0:
           return 0 
        return solve(p1, p2, level - 1)
    if g1[0] == g2[0]:
        return sub(p1, p2, level)
    elif g1[1] == g2[1]:
        return sub((p1[1], p1[0]), (p2[1], p2[0]), level)
    else:
        return abs(p1[0] - p2[0]) + abs(p1[1] - p2[1])

q = int(input())
for i in range(q):
    a, b, c, d = [int(x) - 1 for x in input().split()]
    print(solve((a, b), (c, d), 30))

Solution (Python):
def solve(a, b, c, d):
  mnx = min(a, c)
  mxx = max(a, c)
  mny = min(b, d)
  mxy = max(b, d)
  s = 3
  for k in range(32):
    if a<c:
      rx = (a+s/3*2)/s*s+s/3
      ry = (max(b, d)+s/3)/s*s+s/3
      if rx+s/3<=c and ry+s/3>max(b, d) and ry<=min(b, d):
        mny = min(mny, ry-1)
        mxy = max(mxy, ry+s/3)
        
    else:
      rx = (c+s/3*2)/s*s+s/3
      ry = (max(b, d)+s/3)/s*s+s/3
      if rx+s/3<=a and ry+s/3>max(b, d) and ry<=min(b, d):
        mny = min(mny, ry-1)
        mxy = max(mxy, ry+s/3)
        
    if b<d:
      rx = (max(a, c)+s/3)/s*s+s/3
      ry = (b+s/3*2)/s*s+s/3
      if ry+s/3<=d and rx+s/3>max(a, c) and rx<=min(a, c):
        mnx = min(mnx, rx-1)
        mxx = max(mxx, rx+s/3)
        
    else:
      rx = (max(a, c)+s/3)/s*s+s/3
      ry = (d+s/3*2)/s*s+s/3
      if ry+s/3<=b and rx+s/3>max(a, c) and rx<=min(a, c):
        mnx = min(mnx, rx-1)
        mxx = max(mxx, rx+s/3)
        
    s *= 3
  return min(a-mnx+c-mnx, mxx-a+mxx-c)+min(b-mny+d-mny, mxy-b+mxy-d)

"""
n = 9
F = [[None]*n for _ in range(n)]
def f(x, y, s):
  if s==1:
    return False
  if s/3<=x<s/3*2 and s/3<=y<s/3*2:
    return True
  return f(x%(s/3), y%(s/3), s/3)
for y in range(n):
  for x in range(n):
    F[y][x] = f(x, y, n)

def naive(a, b, c, d):
  D = [[9999]*n for _ in range(n)]
  D[b][a] = 0
  for dd in range(2*n):
    for y in range(n):
      for x in range(n):
        if D[y][x]==dd:
          for i in range(4):
            tx = x + [1, -1, 0, 0][i]
            ty = y + [0, 0, 1, -1][i]
            if 0<=tx<n and 0<=ty<n and not F[ty][tx]:
              D[ty][tx] = min(D[ty][tx], dd+1)
  return D[d][c]

for a in range(n):
  for b in range(n):
    if not F[b][a]:
      for c in range(n):
        for d in range(n):
          if not F[d][c]:
            x = solve(a, b, c, d)
            y = naive(a, b, c, d)
            if x!=y:
              print a, b, c, d, x, y
"""

Q = input()
for q in range(Q):
  a, b, c, d = map(int, raw_input().split())
  a -= 1
  b -= 1
  c -= 1
  d -= 1
  print solve(a, b, c, d)

Solution (Python):
def dist(a,b,c,d,n):
    L=3**n
    area1=(a//L)*3+b//L
    if area1==2:
        b=3*L-b-1
        d=3*L-d-1
    if area1==3:
        a,b=b,a
        c,d=d,c
    if area1==5:
        a,b=3*L-b-1,a
        c,d=3*L-d-1,c
    if area1 in [6,7]:
        a=L*3-a-1
        c=L*3-c-1
    if area1==8:
        a,b=L*3-a-1,L*3-b-1
        c,d=L*3-c-1,L*3-d-1

    area1=(a//L)*3+b//L
    area2=(c//L)*3+d//L

    if area1>8 or area2>8:
        a=0
        while True:
            a+=1
    if n==0:
        if area1==1 and area2==7: return 4
        else: return abs(a-c)+abs(b-d)

    if area1>area2:
        a,b,c,d=c,d,a,b
        area1,area2=area2,area1
    
    if area1==area2:
        return dist(a%L,b%L,c%L,d%L,n-1)

    elif area1==0:
        if area2 in [5,7,8]:
            return abs(a-c)+abs(b-d)
        elif area2 in [3,6]:
            return dist(b,a,d,c,n)

        elif area2 in [1,2]:
            L=3**(n-1)
            a12=(a//L)*3+b//L
            a22=(c//L)*3+(d-3*area2*L)//L
            if a//L!=c//L:
                return abs(a-c)+abs(b-d)
            elif a//L==0:
                p=(d//L)-(b//L)
                if p==1: return dist(a,b-2*L,c,d-2*L,n-1)
                else: return dist(a,b%L,c,d%L+2*L,n-1) +(p-2)*L
            elif a//L==1:
                if area2==1 and a12==5 and a22==3: return dist(a-L,b-2*L,c-L,d-2*L,n)
                else: return min(a+c-2*(L-1),4*L-a-c)+abs(b-d)
            elif a//L==2: return dist(a-2*L,b,c-2*L,d,n)

        else: return 0

    elif area1==1:
        if area2 in [3,5,6,8]:
            return abs(a-c)+abs(b-d)
        elif area2==2:
            return dist(a,b-L,c,d-L,n)
        elif area2==7:
            return min(b+d-2*(L-1),(4*L)-b-d)+abs(a-c)
        else: return 0



for i in range(int(input())):
    a,b,c,d=map(int,input().split())
    print(dist(a-1,b-1,c-1,d-1,29))

Solution (Python):
def between(x, y1, y2):
    if x % 3 != 1:return False
    if y1 > y2:
        y1,y2= y2,y1
    for i in range(10):
        if y1 + i >= y2:break
        if (y1 + i) % 3 == 1:
            return True
    return False
    
def dist(x1, y1, x2, y2):
    three = 1
    extra = 0
    for i in range(33):
        if x1 // three == x2 // three and between(x1 //three, y1 //three, y2//three):
            extra = max(extra, min(min(x1 % three, x2 %three) + 1, three - max(x1 % three, x2 % three)))
        three *= 3

    return abs(x1-x2) + abs(y1-y2) + extra * 2

def solve():
    a,b,c,d = map(int, input().split())
    a,b,c,d = a-1,b-1,c-1,d-1
    print(max(dist(a,b,c,d), dist(b,a,d,c)))

q = int(input())
for _ in range(q):
    solve()

Solution (Python):
import sys
input=sys.stdin.readline

def dist(a,b,c,d,P3):
    for p in P3:
        da,ma=divmod(a,p)
        dc,mc=divmod(c,p)
        if da!=dc:
            return abs(a-c)+abs(b-d)
        if da!=1:
            a,c=ma,mc
            continue
        db,mb=divmod(b,p)
        dd,md=divmod(d,p)
        if abs(db-dd)<2:
            a,c=ma,mc
            continue
        return min(ma+mc+2,2*p-(ma+mc))+abs(b-d)
    return abs(a-c)+abs(b-d)

def main():
    q=int(input())
    P3=[pow(3,i) for i in reversed(range(30))]
    for _ in range(q):
        a,b,c,d=map(lambda x: int(x)-1,input().split())
        print(max(dist(a,b,c,d,P3),dist(b,a,d,c,P3)))

if __name__=='__main__':
    main()

Solution (Python):
def solve():
    a, b, c, d = map(int, input().split())
    a -= 1
    b -= 1
    c -= 1
    d -= 1
    if a > c:
        a, b, c, d = c, d, a, b
    for k in range(30, -1, -1):
        def check(a, b, c, d):
            if a // 3 ** k == c // 3 ** k and a // 3 ** k % 3 == 1 \
                    and (min(b, d) // 3 ** k % 3 == 0 and max(b, d) // 3 ** k % 3 == 2
                            or max(b, d) // 3 ** k - min(b, d) // 3 ** k >= 3):
                print(min(a % 3 ** k + 1 + c % 3 ** k + 1 + abs(b - d),
                    3 ** k - a % 3 ** k + 3 ** k - c % 3 ** k + abs(b - d)))
                return True
        if check(a, b, c, d) or check(b, a, d, c):
            return
    print(abs(a - c) + abs(b - d))

q = int(input())
for _ in range(q):
    solve()

Solution (Python):

def between(x,y1,y2):
    if y1>y2:y1,y2=y2,y1
    y1+=1;y2-=1
    if not(y1<=y2):
        return False
    while(x>0):
        if x%3==1:
            if y2-y1>3:
                return True
            for y in range(y1,y2+1):
                if y%3==1:
                    return True
        x//=3
        y1//=3
        y2//=3
    return False
def get_extra(x1,y1,x2,y2):
    ans=0
    three=1
    for i in range(35):
        if(x1//three==x2//three and between(x1//three,y1//three,y2//three)):
            tmp=min(min(x1%three,x2%three)+1,three-max(x1%three,x2%three))
            ans=max(ans,tmp)
        three*=3
    return ans
def get_dist(x1,y1,x2,y2):
    return abs(x1-x2)+abs(y1-y2)+2*max(get_extra(x1,y1,x2,y2),get_extra(y1,x1,y2,x2))
Q=int(input())
for i in range(Q):
    a,b,c,d=map(int,input().split())
    print(get_dist(a-1,b-1,c-1,d-1))

Solution (Python):
import sys


def solve(a, b, c, d):
    """ Lv.i の中央の■を、上下(a,c)に迂回する """
    for i in range(30, 0, -1):
        
        d3i = d3[i - 1]
        da, ma = divmod(a, d3i)
        dc, mc = divmod(c, d3i)
        if da != dc:
            return abs(a - c) + abs(b - d)
        if da != 1:
            a, c = ma, mc
            continue
        db, mb = divmod(b, d3i)
        dd, md = divmod(d, d3i)
        if (abs(db - dd) < 2):
            a, c = ma, mc
            continue
        return min(ma + mc + 2, 2 * d3i - (ma + mc)) + abs(b - d)
    return abs(a - c) + abs(b - d)


d3 = [pow(3, i) for i in range(31)] + [0]

q = int(input())
buf = []
for line in sys.stdin:
    a, b, c, d = map(int, line.split())
    a -= 1
    b -= 1
    c -= 1
    d -= 1
    ans = max(solve(a, b, c, d), solve(b, a, d, c))
    buf.append(ans)
print('\n'.join(map(str, buf)))

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
def solve(A,B,C,D,E=3**30):
    
    if not E:
        return abs(A-C) + abs(B-D)
    a = A//E
    b = B//E
    c = C//E
    d = D//E
    if a != c and b != d:
        return abs(A-C) + abs(B-D)
    if a == c and b == d:
        return solve(A,B,C,D,E//3)
    if b == d and a != c:
        A,B = B,A
        a,b = b,a
        C,D = D,C
        c,d = d,c
    if a == c and b != d:
        if a % 3 != 1:
            return solve(A,B,C,D,E//3)
        if abs(b-d) == 1:
            return solve(A,B,C,D,E//3)
        if B > D:
            A,B,C,D = C,D,A,B
            a,b,c,d = c,d,a,b
        x1 = E * a - 1
        y1 = E * (b+1) - 1
        y2 = E * d
        dist1 = abs(x1-A) + abs(y1-B) + abs(y1-y2) + abs(x1-C) + abs(y2-D)
        x1 = E * (a+1)
        y1 = E * (b+1) - 1
        y2 = E * d
        dist2 = abs(x1-A) + abs(y1-B) + abs(y1-y2) + abs(x1-C) + abs(y2-D)
        return min(dist1, dist2)
 
solve(2,1,3,1)
 
N = int(readline())
m = map(int,read().split())
for A,B,C,D in zip(m,m,m,m):
    print(solve(A-1,B-1,C-1,D-1,3**30))

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

def solve(A,B,C,D,E=3**30):
    
    if not E:
        return abs(A-C) + abs(B-D)
    a = A//E
    b = B//E
    c = C//E
    d = D//E
    if a != c and b != d:
        return abs(A-C) + abs(B-D)
    if a == c and b == d:
        return solve(A,B,C,D,E//3)
    if b == d and a != c:
        A,B = B,A
        a,b = b,a
        C,D = D,C
        c,d = d,c
    if a == c and b != d:
        if a % 3 != 1:
            return solve(A,B,C,D,E//3)
        if abs(b-d) == 1:
            return solve(A,B,C,D,E//3)
        if B > D:
            A,B,C,D = C,D,A,B
            a,b,c,d = c,d,a,b
        x1 = E * a - 1
        y1 = E * (b+1) - 1
        y2 = E * d
        dist1 = abs(x1-A) + abs(y1-B) + abs(y1-y2) + abs(x1-C) + abs(y2-D)
        x1 = E * (a+1)
        y1 = E * (b+1) - 1
        y2 = E * d
        dist2 = abs(x1-A) + abs(y1-B) + abs(y1-y2) + abs(x1-C) + abs(y2-D)
        return min(dist1, dist2)

solve(2,1,3,1)

N = int(readline())
m = map(int,read().split())
for A,B,C,D in zip(m,m,m,m):
    print(solve(A-1,B-1,C-1,D-1,3**30))

Solution (Python):
def calc(a, b, c, d):
    if abs(c - a) < abs(d - b): a, b, c, d = b, a, d, c
    if c < a: a, b, c, d = c, d, a, b
    
    s = 3 ** 29
    while s:
        bb = b // s
        dd = d // s
        if bb != dd: return c - a + abs(d - b)
        if bb % 3 == 1 and c // s - a // s >= 2:
            l = bb * s - 1
            r = (bb + 1) * s
            return c - a + min(b + d - 2 * l, 2 * r - b - d)
        s //= 3
    return c - a + abs(d - b)

Q = int(input())
for _ in range(Q):
    a, b, c, d = map(int, input().split())
    print(calc(a-1, b-1, c-1, d-1))