/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author aajisaka
 */

#include<bits/stdc++.h>

using namespace std;

void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

#define SPEED ios_base::sync_with_stdio(false);cin.tie(nullptr)
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define all(v) v.begin(), v.end()
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

using ll = long long;
using P = pair<ll, ll>;

constexpr long double PI = 3.14159265358979323846264338327950288L;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

class FFractalShortestPath {
public:

    vector<ll> e3;

    ll calc(ll a, ll b, ll c, ll d) {
      a--; b--; c--; d--;
      for(int i=29; i>=0; i--) {
        //debug(i);
        auto e = e3[i];
        auto a3 = a/e;
        auto b3 = b/e;
        auto c3 = c/e;
        auto d3 = d/e;
        if (a3 != c3 && b3 != d3) {
          return abs(b-d) + abs(a-c);
        }
        //debug(a3, b3, c3, d3);
        if (a3 == c3 && b3 == d3) {
          a %= e;
          b %= e;
          c %= e;
          d %= e;
          continue;
        }

        if (a3 != c3) {
          swap(a, b); swap(c, d);
          swap(a3, b3); swap(c3, d3);
        }
        //debug(a, b, c, d);

        // a3 == c3, b3 != d3
        while(a3 == c3 && e > 0) {
          //debug(a, c, a3, c3, e);
          if (a3%3 == 1 && c3%3 == 1 && abs(b/e-d/e) > 1) {
            ll left = a%e+c%e+2;
            ll right = e*2-a%e-c%e;
            return abs(b-d)+min(left, right);
          }
          e /= 3;
          if (e==0) break;
          a3 = a/e;
          c3 = c/e;
          //debug(a3, c3, e);
        }
        return abs(b-d) + abs(a-c);
      }
      return abs(b-d) + abs(a-c);
    }

    void solve(istream& cin, ostream& cout) {
      SPEED;
      int q; cin >> q;
      e3.resize(31, 1);
      for(int i=1; i<=30; i++) {
        e3[i] = e3[i-1]*3;
      }
      while(q--) {
        ll a, b, c, d;
        cin >> a >> b >> c >> d;
        cout << calc(a, b, c, d) << '\n';
      }
    }
};

signed main() {
  FFractalShortestPath solver;
  std::istream& in(std::cin);
  std::ostream& out(std::cout);
  solver.solve(in, out);
  return 0;
}