#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){
    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]);
        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){
    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];
    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);
        }
        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;
}

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);
    }
    return 0;
}


Measured memory_bytes: 384