# Original solution
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-(p-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(eval(input()))):
    a,b,c,d=list(map(int,input().split()))
    print((dist(a-1,b-1,c-1,d-1,29)))

# Optimized solution
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(eval(input()))):
    a,b,c,d=list(map(int,input().split()))
    print((dist(a-1,b-1,c-1,d-1,29)))