#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <algorithm>
#include <complex>
#include <array>
#include <functional>
using namespace std;
 
#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define ALL(c) (c).begin(), (c).end()
 
typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<double> VD;
typedef vector<VI> VVI;
typedef vector<VL> VVL;
typedef vector<VD> VVD;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;

template<typename T> void chmin(T &a, T b) { if (a > b) a = b; }
template<typename T> void chmax(T &a, T b) { if (a < b) a = b; }

int in() { int x; scanf("%d", &x); return x; }
ll lin() { ll x; scanf("%lld", &x); return x; }

const int N = 30;
ll three[N + 1];

ll calc2(ll x1, ll y1, ll x2, ll y2, ll n){
    // cout << "calc2" << endl;
    // cout << x1 << " " << y1 << "  " << x2 << " " << y2 << "   " << n << endl;
    ll d = abs(x1 - x2) + abs(y1 - y2);
    if (n == 0) return d;
    if (y1 > y2){
        swap(x1, x2);
        swap(y1, y2);
    }
    y2 -= y1 / three[n] * three[n];
    y1 %= three[n];
    ll bx1 = x1 / three[n - 1];
    ll by1 = y1 / three[n - 1];
    ll bx2 = x2 / three[n - 1];
    ll by2 = y2 / three[n - 1];
    if (bx1 == bx2){
        if (bx1 != 1){
            return calc2(x1 % three[n - 1], y1, x2 % three[n - 1], y2, n - 1);
        }
        if (by1 == 2 && by2 == 3){
            return calc2(x1 - three[n - 1], y1 - 2 * three[n - 1], x2 - three[n - 1], y2 - 2 * three[n - 1], n - 1);
        }
        ll du1 = x1 - (y1 % three[n - 1]);
        ll dl1 = (2 * three[n - 1] - x1) + (three[n - 1] - (y1 % three[n - 1])) - 1;
        ll du2 = x2 - three[n - 1] + (y2 % three[n - 1]) + 1;
        ll dl2 = (2 * three[n - 1] - x2) + (y2 % three[n - 1]);
        // cout << du1 << " " << dl1 << "  " << du2 << " " << dl2 << endl;
        return min(du1 + du2, dl1 + dl2) + (by2 - by1 - 1) * three[n - 1] + 1;
    }
    return d;
}

ll calc(ll x1, ll y1, ll x2, ll y2, ll n){
    // cout << "calc" << endl;
    ll d = abs(x1 - x2) + abs(y1 - y2);
    ll bx1 = x1 / three[n - 1];
    ll by1 = y1 / three[n - 1];
    ll bx2 = x2 / three[n - 1];
    ll by2 = y2 / three[n - 1];
    // cout << bx1 << " " << by1 << "   " << bx2 << " " << by2 << endl;
    if (bx1 == bx2 && by1 == by2){
        return calc(x1 % three[n - 1], y1 % three[n - 1], x2 % three[n - 1], y2 % three[n - 1], n - 1);
    }
    if ((bx1 == bx2 && bx1 == 1 && abs(by1 - by2) == 2) || (by1 == by2 && by1 == 1 && abs(bx1 - bx2) == 2)){
        if (by1 == 1){
            swap(x1, y1);
            swap(x2, y2);
        }
        if (y1 > y2){
            swap(x1, x2);
            swap(y1, y2);
        }
        // cout << x1 << " " << y1 << "   " << x2 << " " << y2 << endl;
        ll du1 = abs(three[n - 1] - 1 - x1) + abs(three[n - 1] - 1 - y1);
        ll dl1 = abs(2 * three[n - 1] - x1) + abs(three[n - 1] - 1 - y1);
        ll du2 = abs(three[n - 1] - 1 - x2) + abs(2 * three[n - 1] - y2);
        ll dl2 = abs(2 * three[n - 1] - x2) + abs(2 * three[n - 1] - y2);
        return min(du1 + du2, dl1 + dl2) + three[n - 1] + 1;
    }
    if (bx1 == bx2){
        return calc2(x1 % three[n - 1], y1, x2 % three[n - 1], y2, n - 1);
    }
    if (by1 == by2){
        return calc2(y1 % three[n - 1], x1, y2 % three[n - 1], x2, n - 1);
    }
    return d;
}

VVI field(int n){
    int m = 1;
    REP(i,n) m *= 3;
    VVI ret(m, VI(m));
    m /= 3;
    if (n == 0) return ret;
    VVI f = field(n - 1);
    REP(i,3) REP(j,3){
        REP(x,m) REP(y,m){
            ret[i*m+x][j*m+y] = ((i == 1 && j == 1) || f[x][y]);
        }
    }
    return ret;
}

int di[] = {-1, 1, 0, 0}, dj[] = {0, 0, -1, 1};
int naive(int x1, int y1, int x2, int y2){
    VVI f = field(3);
    int n = f.size();
    VVI dist(n, VI(n, -1));
    dist[x1][y1] = 0;
    queue<P> que;
    que.push(P(x1, y1));
    while (!que.empty()){
        P p = que.front();
        que.pop();
        int i = p.first, j = p.second;
        REP(k,4){
            int ii = i + di[k], jj = j + dj[k];
            if (ii < 0 || ii >= n || jj < 0 || jj >= n || f[ii][jj] || dist[ii][jj] != -1) continue;
            dist[ii][jj] = dist[i][j] + 1;
            que.push(P(ii, jj));
        }
    }
    return dist[x2][y2];
}

int main(void){
    three[0] = 1;
    REP(i,N) three[i + 1] = 3 * three[i];
    int q;
    cin >> q;
    while (q--){
        ll a = lin()-1;
        ll b = lin()-1;
        ll c = lin()-1;
        ll d = lin()-1;
        ll x = calc(a, b, c, d, N);
        printf("%lld\n", x);
    }
    // VVI f = field(3);
    // int n = f.size();
    // REP(i,n){
    //     REP(j,n) cout << f[i][j];
    //     cout << endl;
    // }
    // REP(x1,n) REP(y1,n) REP(x2,n) REP(y2,n){
    //     if (f[x1][y1] || f[x2][y2] || (x1 == x2 && y1 == y2)) continue;
    //     ll d1 = calc(x1, y1, x2, y2, N);
    //     ll d2 = naive(x1, y1, x2, y2);
    //     if (d1 != d2){
    //         cout << x1 << " " << y1 << "  " << x2 << " " << y2 << endl;
    //     }
    // }
    return 0;
}


Measured memory_bytes: 384