// Copyright [2020] <unknown>
#include <bits/stdc++.h>
using namespace std;
#define ONLINE_JUDGE
#ifndef ONLINE_JUDGE
#define dbg(x...) { cerr << "\033[32;1m" << #x << " -> "; err(x); }
void err() { cerr << "\033[39;0m" << endl; }
template<typename T, typename... A>
void err(T a, A... x) { cerr << a << ' '; err(x...); }
#else
#define dbg(...)
#endif

#define sz(x) ((int)x.size())

typedef long long LL;

typedef pair<LL, LL> P;

P s, t;

LL p3[100];


int findK(const P &p) {
    int k = 0;
    LL mx = max(p.first, p.second);
    while (p3[k] < mx)
        ++k;
    return k;
}

P idp(const P &p, int k) {
    if (k == 0)
        return p;
    else {
        return P(p.first / p3[k-1] % 3, p.second / p3[k-1] % 3);
    }
}

LL dis(const P &a, const P &b) {
    return llabs(a.first - b.first) + llabs(a.second - b.second);
}

P basep(const P &p, int k) {
    return P(p.first / p3[k] * p3[k], p.second / p3[k] * p3[k]);
}

int main(int argc, char const *argv[]) {
    // code
    p3[0] = 1;
    for (int i=1; i<=30; ++i)
        p3[i] = p3[i-1] * 3;
    // dbg(p3[30]);
    int tt; scanf("%d", &tt);
    for (int kk=0; kk<tt; ++kk) {
        // cin >> s.first >> s.second >> t.first >> t.second;
        scanf("%lld%lld%lld%lld", &s.first, &s.second, &t.first, &t.second);
        if (s == t) {
            puts("0");
            continue;
        }
        --s.first; --t.first;
        --s.second; --t.second;
        if (llabs(s.first - t.first) < llabs(s.second - t.second)) {
            swap(s.first, s.second);
            swap(t.first, t.second);
        }
        if (s.first > t.first)
            swap(s, t);
        // int k = max(findK(s), findK(t));


        // LL ans = dis(s, t);
        // P ids = idp(s, k), idt = idp(t, k);
        // while ()

        LL ans = dis(s, t);
        // dbg(s.first, s.second, t.first, t.second);
        for (int k=30; k>=1; --k) {
            P ids = idp(s, k), idt = idp(t, k);
            if (basep(s, k-1) == basep(t, k-1))
                continue;
            dbg(ids.first, ids.second, idt.first, idt.second, k);
            if (ids.second == 1 && (ids.first == 0 || idt.first == 2 || llabs(s.first - t.first) > p3[k])) {
                // LL l = p3[k-1]-1, r = 2 * p3[k-1];
                // LL sx = s.second % p3[k], st = t.second % p3[k];
                // ans += min(sx + st - 2 * l, 2 * r - sx - st);
                P bp = basep(s, k);
                // dbg(bp.first, bp.second);
                P l(s.first, bp.second + p3[k-1] - 1),
                r(s.first, bp.second + 2 * p3[k-1]);
                ans = min(dis(s, l) + dis(l, t), dis(s, r) + dis(r, t));
                break;
            }
        }


        printf("%lld\n", ans);
    }
    return 0;
}
