#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<math.h>
#include<iomanip>
#include<set>
#include<numeric>
#include<cstring>
#include<cstdio>
#include<functional>
#include<bitset>
#include<limits.h>
#include<cassert>
#include<iterator>
#include<complex>
#include<stack>
#include<unordered_map>
#include<unordered_set>
#include<time.h>
#include<random>
#include<array>
using namespace std;
using ll = long long;
using ull = unsigned long long;
#define rep(i, a, b) for(int i = a; i < b; i++)
#define rrep(i, a, b) for(int i = b - 1; i >= a; i--)
#define repl(i, a, b) for(long long i = a; i < b; i++)
#define rrepl(i, a, b) for(long long i = b - 1; i >= a; i--)
#define ALL(a) a.begin(), a.end()
using pii = pair<int,int>;
using piii = pair<pii,int>;
using pll = pair<long long, long long>;
using plll = pair<pll, long long>;

template<class T>inline bool chmax(T &a, const T &b) {if(a<b){a = b; return 1;} return 0; };
template<class T>inline bool chmin(T &a, const T &b) {if(a>b){a = b; return 1;} return 0; };
void iosetup() {
    cin.tie(nullptr);ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);
    cerr << fixed << setprecision(10);
}
//----------------------- edit from here ---------------------------------

bool between(ll x, ll y1, ll y2){
    if(y1 > y2) swap(y1, y2);
    y1++, y2--;
    if(!(y1 <= y2)) return false;

    while(x > 0){
        if(x % 3 == 1){
            if(y2 - y1 > 3) return true;
            repl(y, y1, y2 + 1) if(y % 3 == 1) return true;
        }
        x /= 3; y1 /= 3; y2 /= 3;
    }
    return false;
}

ll get_extra(ll x1, ll y1, ll x2, ll y2){
    ll ans = 0;
    ll three = 1;
    rep(i, 0, 35){
        if(x1 / three == x2 / three and 
            between(x1 / three, y1 / three, y2 / three)){
            ll tmp = min(min(x1 % three, x2 % three) + 1,
                 three - max(x1 % three, x2 % three));
            chmax(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(){
    iosetup();
    int Q; cin >> Q;
    while(Q--){
        ll a, b, c, d; cin >> a >> b >> c >> d; a--, b--, c--, d--;       
        cout << get_dist(a, b, c, d) << endl;
    }
    return 0;
}