// 2020-08-07 18:30:38
#include<bits/stdc++.h>
#ifdef LOCAL
#include "lib/debug.hpp"
#else
#define debug(...) 1
#endif
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define rep(i, n) REP(i, 0, (n))
#define repc(i, n) REPC(i, 0, (n))
#define REP(i, n, m) for (int i = (int)(n); i < (int)(m); i++)
#define REPC(i, n, m) for (int i = (int)(n); i <= (int)(m); i++)
#define REPCM(i, n, m) for (int i = (int)(n); i >= (int)(m); i--)
using namespace std;
using ll = long long;
using ld = long double;
using pr = pair<ll, ll>;
using vll = vector<ll>;
using vpr = vector<pr>;
using P = pair<int, int>;
template<class T> inline bool chmin(T& a, const T& b) { if (a > b) { a = b; return true; } else return false; }
template<class T> inline bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } else return false; }

int q;
ll r1, c1, r2, c2, pow3[40];
void solve() {
  REPCM(k, 30, 1) {
    int j = k - 1;
    bool interrupted = true;
    interrupted &= (r1 / pow3[j] + 2 <= r2 / pow3[j]);
    interrupted &= (c1 / pow3[j] == c2 / pow3[j]);
    interrupted &= ((c1 / pow3[j]) % 3 == 1);
    if(interrupted) {
      int j = k - 1;
      ll l = c1 / pow3[j] * pow3[j];
      ll r = l + pow3[j];
      ll cd = min(c1-l+c2-l+2, r-c1+r-c2);
      cout << r2-r1+cd << '\n';
      return;
    }
  }
  cout << abs(r2-r1) + abs(c2-c1) << '\n';
}
void answer() {
  cin >> q;
  pow3[0] = 1;
  rep(i, 35) pow3[i+1] = pow3[i] * 3;
  auto normalize = [&]() {
    r1--; r2--; c1--; c2--;
    if(abs(r1-r2) < abs(c1-c2)) {
      swap(r1, c1);
      swap(r2, c2);
    }
    if(r1 > r2) {
      swap(r1, r2);
      swap(c1, c2);
    }
  };
  rep(qi, q) {
    cin >> r1 >> c1 >> r2 >> c2;
    normalize();
    solve();
  }
}
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);
  answer();
  return 0;
}