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
        C = 2 - C
    if b > d:
        B = 2 - B
        D = 2 - 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))
                        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(1)
                                    end = True
                                continue
                        else:
                            if j == k:
                                ans.append(dis)
                                end = True
                            continue
for a in ans:
    print(a)

### FIXED CODE ###

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)