#include <iostream>
#include <algorithm>
using namespace std;

typedef long long ll;
using ll = long long;

bool between(ll x, ll y1, ll y2){
    if(y1 > y2) swap(y1, y2);

    if(x % 3 == 1){
        if(y2 - y1 >= 3) return true;
        for(ll y=y1;y<=y2;y++) if(y % 3 == 1) return true;
    }

    return false;
}

ll get_extra(ll x1, ll y1, ll x2, ll y2) {
    ll ans = 0;
    ll three = 1;
    for (int i = 0; i < 35; ++i) {
        if(x1 / three == x2 / three && between(x1 / three, y1 / three, y2 / three)) {
            ll tmp = min(min(x1 % three, x2 % three) + 1, three - max(x1 % three, x2 % three));
            ans = max(ans, tmp);
        }
        three *= 3;
    }

    return ans;
}

ll get_dist(ll x1, ll y1, ll x2, ll y2){
    return abs(x1 - x2) + abs(y1 - y2) + 2 * max(get_extra(x1, y1, x2, y2), get_extra(y1, x1, y2, x2));
}

int main() {
    int Q;
    cin >> Q;

    while (Q--) {
        long long a;
        long long b;
        long long c;
        long long d;

        cin >> a >> b >> c >> d;
        cout << get_dist(a-1, b-1, c-1, d-1) << endl;
    }

    return 0;
}