#include <bits/stdc++.h>

using namespace std;

template <class TH> void _dbg(const char *sdbg, TH h){cerr<<sdbg<<"="<<h<<"\n";}
template<class TH, class... TA> void _dbg(const char *sdbg, TH h, TA... a) {
  while(*sdbg!=',')
    cerr<<*sdbg++;
  cerr<<"="<<h<<","; 
  _dbg(sdbg+1, a...);
}

template<class T> ostream & operator<<(ostream & os, vector<T> V){
  os<<"[";
  for(auto vv: V) os << vv <<",";
  return os << "]";
}
template<class L, class R> ostream & operator <<(ostream & os, pair<L,R> P){
  return os <<"("<<P.first <<","<<P.second <<")";
}

#ifdef LOCAL
#define debug(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
#else
#define debug(...) (__VA_ARGS__)
#define cerr if(0)cout
#endif

long long pot[35];


long long solve2(long long xa, long long xb, int level) {
    if (level == 0) {
        return abs(xb - xa);
    }
    int ra = xa / pot[level - 1];
    int rb = xb / pot[level - 1];
    if (ra == rb) {
        if (ra == 1) {
            xa = xa % pot[level - 1];
            xb = xb % pot[level - 1];
            return min(xa + xb + 2, pot[level - 1] - xa + pot[level - 1] - xb);
        }
        if (rb == 2) {
            xa = xa % pot[level - 1];
            xb = xb % pot[level - 1];
        }
        return solve2(xa, xb, level - 1);
    } else {
        return abs(xa - xb);
    }
}


long long solve3(long long xa, long long xb, long long y, int dir, int level) {
//     cerr << xa << " " << xb << " " << y << " " << level << endl;
    if (level == 0) {
        return abs(xa - xb);
    }
    if (dir == 1) {
        y = pot[level] - y - 1;
        return solve3(xa, xb, y, 0, level);
    }
    int ra = xa / pot[level - 1];
    int rb = xb / pot[level - 1];
    int c = y / pot[level - 1];
    
    if (ra == rb) {
        if (c == 0) {
            return solve3(xa % pot[level - 1], xb % pot[level - 1], y % pot[level - 1], 0, level - 1);
        }
//         if (ra == 1) {
//             xa = xa % pot[level - 1];
//             xb = xb % pot[level - 1];
//             return min(xa + xb + 2, pot[level - 1] - xa + pot[level - 1] - xb);
//         }
//         if (rb == 2) {
//             xa = xa % pot[level - 1];
//             xb = xb % pot[level - 1];
//         }
        if (c == 1) return solve2(xa % pot[level - 1], xb % pot[level - 1], level - 1);
        return solve2(xa, xb, level);
    } else {
        return abs(xa - xb);
    }
}

long long solve(long long xa, long long ya, long long xb, long long yb, int level) {    

    if (level == 0) {
        return abs(xb - xa) + abs(yb - ya);
    }
    int ra = xa / pot[level - 1];
    int ca = ya / pot[level - 1];
    int rb = xb / pot[level - 1];
    int cb = yb / pot[level - 1];
    if (ra == rb && ca == cb) {
        return solve(xa % pot[level - 1], ya % pot[level - 1], xb % pot[level - 1], yb % pot[level - 1], level - 1);
    }
    
    if (ra != rb && ca != cb) {
        return abs(xa - xb) + abs(ya - yb);
    }
    if (ra == rb) {
        long long d = abs(ya - yb);
        if (abs(cb - ca) == 2) {
            return d + solve2(xa, xb, level);
        }
//         cerr << max(solve3(xa % pot[level - 1], xb % pot[level - 1], min(ya, yb) % pot[level - 1], 1, level - 1), solve3(xa, xb, max(ya, yb) % pot[level - 1], 0, level - 1)) << endl;
        return d + max(solve3(xa % pot[level - 1], xb % pot[level - 1], min(ya, yb) % pot[level - 1], 1, level - 1), solve3(xa % pot[level - 1], xb % pot[level - 1], max(ya, yb) % pot[level - 1], 0, level - 1));
    }
    if (ca == cb) {
        long long d = abs(xa - xb);
        if (abs(rb - ra) == 2) {
            return d + solve2(ya, yb, level);
        }
        return d + max(solve3(ya % pot[level - 1], yb % pot[level - 1], min(xa, xb) % pot[level - 1], 1, level - 1), solve3(ya % pot[level - 1], yb % pot[level - 1], max(xa, xb) % pot[level - 1], 0, level - 1));
    }
    return 0;
}

int main() {
    pot[0] = 1;
    for (int i = 1; i <= 30; i++) {
        pot[i] = pot[i - 1] * 3;
    }
    int t;
    scanf("%d", &t);
    while (t--) {
        long long xa, xb, ya, yb;
        scanf("%lld %lld %lld %lld", &xa, &ya, &xb, &yb);
        xa--;
        ya--;
        xb--;
        yb--;
        printf("%lld\n", solve(xa, ya, xb, yb, 30));
    }
    return 0;
}


Measured memory_bytes: 384