#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;
}

int Minus(vector<int> &d, int pos)
{
    for (int a = pos; a >= 0; a--)
    {
        d[a]--;
        if (d[a] != -1) return 1;
        d[a] = 2;
    }
    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";
}

const int N = 27;

string s[N];
int dist[N][N];

bool ok(int x, int y)
{
    return 0 <= x && x < N && 0 <= y && y < N && s[x][y] == '.';
}

int cx[4] = {0, 0, -1, 1};
int cy[4] = {1, -1, 0, 0};

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

    int t;
    cin >> t;
    while (t--) solve();
    return 0;

    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            vector<int> a = three(i), b = three(j);
            int t = 0;
            for (int k = 0; k < 30; k++) if (a[k] == 1 && b[k] == 1) t = 1;
            if (t) s[i] += "#";
            else s[i] += ".";
        }
    }
    int c1, d1;
    cin >> c1 >> d1;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            dist[i][j] = -1;
        }
    }

    vector<pair<int, int> > q = {{c1, d1}};
    dist[c1][d1] = 0;
    for (int i = 0; i < q.size(); i++)
    {
        int x = q[i].first, y = q[i].second;
        for (int k = 0; k < 4; k++)
        {
            int nx = x + cx[k];
            int ny = y + cy[k];
            if (ok(nx, ny) && dist[nx][ny] == -1)
            {
                dist[nx][ny] = dist[x][y] + 1;
                q.push_back({nx, ny});
            }
        }
    }

    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if (s[i][j] != '#' && dist[i][j] != solve(i, j, c1, d1))
            {
                cout << "WA " << i << " " << j << " " << c1 << " " << d1 << " EXP: " << dist[i][j] << " MY: " << solve(i, j, c1, d1) << "\n";
                //cout << "*#&(#^$%^*$";
                //exit(485);
            }
        }
    }
}


Measured memory_bytes: 384