#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<int(n);++i)
typedef long long ll;

vector<ll> width = {1LL};

ll solve(ll s1, ll s2, ll l1, ll l2, int level){
    if (level == 0) return abs(l1-l2);
    ll w = width[level-1];
    if (s1/w != s2/w) {
        return abs(s1-s2) + abs(l1-l2);
    } else if (s1/w == 1 && abs(l1/w - l2/w) >= 2) {
        return min(s1%w + s2%w + 2, w*2 - s1%w - s2%w) + abs(l1-l2);
    } else {
        return solve(s1%w, s2%w, l1, l2, level-1);
    }
}

int main(void){
    rep(i,30){
        width.push_back(width.back() * 3LL);
    }
    int Q;
    cin >> Q;
    rep(q,Q){
        ll a,b,c,d;
        cin >> a >> b >> c >> d;
        a--,b--,c--,d--;
        if (abs(a-c) > abs(b-d)) {
            swap(a,b), swap(c,d);
        }
        cout << solve(a,c,b,d,30) << endl;
    }
    return 0;
}
