#include <bits/stdc++.h>

typedef long long ll;

using namespace std;

const ll MOD = 1e9 + 7;

#define all(x) (x).begin(), (x).end()
#define int long long

vector<int> three(ll x)
{
    vector<int> a;
    for (int i = 0; i < 30; i++) a.push_back(x % 3), x /= 3;
    reverse(all(a));
    return a;
}

ll num(vector<int> th)
{
    ll x = 0;
    for (int i = 0; i < th.size(); i++) x = x * 3 + th[i];
    return x;
}

int Plus(vector<int> &d, int pos)
{
    for (int a = pos; a >= 0; a--)
    {
        d[a]++;
        if (d[a] != 3) return 1;
        d[a] = 0;
    }
    return 0;
}

ll penalty(ll x1, ll y1, ll x2, ll y2)
{
    vector<int> a1 = three(x1), b1 = three(y1), a2 = three(x2), b2 = three(y2);
    for (int i = 0; i < 30; i++)
    {
        if (a1[i] == a2[i] && b1[i] == b2[i])
        {
            a1[i] = 0, a2[i] = 0, b1[i] = 0, b2[i] = 0;
            x1 = num(a1);
            x2 = num(a2);
            y1 = num(b1);
            y2 = num(b2);
            continue;
        }
        if (a1[i] != a2[i] && b1[i] != b2[i])
        {
            return 0;
        }
        if (b1[i] == b2[i])
        {
            swap(a1, b1);
            swap(a2, b2);
            swap(x1, y1);
            swap(x2, y2);
        }
        if (a1[i] == 1 && a2[i] == 1)
        {
            vector<int> g1(30, 0);
            for (int j = i + 1; j < 30; j++) g1[j] = 2;
            ll r1 = num(g1);
            vector<int> g2(30, 0);
            g2[i] = 2;
            ll r2 = num(g2);
            ll pen1 = min(x1, x2) - r1;
            ll pen2 = r2 - max(x1, x2);
            return 2 * min(pen1, pen2);
        }
        if (y1 > y2)
        {
            swap(y1, y2);
            swap(x1, x2);
            swap(a1, a2);
            swap(b1, b2);
        }
        //cout << "PENALTY IS EQUAL TO " << x1 << " " << y1 << " " << x2 << " " << y2 << "\n";
        for (int j = i + 1; j < 30; j++)
        {
            if (a1[j] != a2[j]) return 0;
            if (a1[j] != 1)
            {
                a1[j] = 0, a2[j] = 0, x1 = num(a1), x2 = num(a2);
                continue;
            }
            vector<int> s1 = b1;
            for (int k = j + 1; k < 30; k++) s1[k] = 0;
            while (s1[j] != 1)
            {
                if (Plus(s1, j) == 0) return 0;
            }
            ll col1 = num(s1);
            if (y1 < col1 && col1 < y2)
            {
                vector<int> r1 = a1;
                for (int k = j + 1; k < 30; k++) r1[k] = 2;
                r1[j]--;
                ll R1 = num(r1);
                ll pen1 = min(x1, x2) - R1;
                vector<int> r2 = a1;
                for (int k = j + 1; k < 30; k++) r2[k] = 0;
                r2[j]++;
                assert(r2[j] <= 2);
                ll R2 = num(r2);
                ll pen2 = R2 - max(x1, x2);
                assert(R1 < x1);
                assert(x1 < R2);
                assert(R1 < x2);
                assert(x2 < R2);
                return 2 * min(pen1, pen2);
            }
        }
        return 0;
    }
    return 0;
}

long long solve(ll x1, ll y1, ll x2, ll y2)
{
    return abs(x1 - x2) + abs(y1 - y2) + penalty(x1, y1, x2, y2);
}

void solve()
{
    ll x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;
    x1--, y1--, x2--, y2--;
    cout << solve(x1, y1, x2, y2) << "\n";
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int t;
    cin >> t;
    while (t--) solve();
}


Measured memory_bytes: 384