#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr int LOGNMAX = 35;
ll pow3[LOGNMAX];
vector<ll> closestLanders(ll yc, ll xc, ll sqSize, bool rightIsGoal) {
  if (sqSize == 1) return {0, 0};
  ll subRange = sqSize / 3;
  if (yc < subRange)
    return closestLanders(yc % subRange, xc % subRange, subRange, rightIsGoal);
  else if (yc >= 2 * subRange) {
    vector<ll> recAns =
        closestLanders(yc % subRange, xc % subRange, subRange, rightIsGoal);
    return {recAns[0] + 2 * subRange, recAns[1] + 2 * subRange};
  } else if ((xc >= 2 * subRange) == (rightIsGoal)) {
    vector<ll> recAns =
        closestLanders(yc % subRange, xc % subRange, subRange, rightIsGoal);
    return {recAns[0] + subRange, recAns[1] + subRange};
  } else
    return {subRange - 1, 2 * subRange};
}
ll solve(ll xa, ll ya, ll xb, ll yb, ll sqSize) {
  if (sqSize == 1) return 0;
  ll subRange = sqSize / 3;
  ll abx = xa / subRange, aby = ya / subRange;
  ll bbx = xb / subRange, bby = yb / subRange;
  if (abx == bbx && aby == bby) {
    return solve(xa % subRange, ya % subRange, xb % subRange, yb % subRange,
                 subRange);
  }
  if (aby == 1 && bby == 1) {
    swap(xa, ya);
    swap(xb, yb);
    swap(abx, aby);
    swap(bbx, bby);
  }
  if (abx == 1 && bbx == 1) {
    return abs(yb - ya) +
           min(xa + xb - 2 * (subRange - 1), 4 * subRange - xa - xb);
  }
  if (abx == bbx || aby == bby) {
    if (aby == bby) {
      swap(xa, ya);
      swap(xb, yb);
      swap(abx, aby);
      swap(bbx, bby);
    }
    if (xa > xb) {
      swap(xa, xb);
      swap(ya, yb);
      swap(abx, bbx);
      swap(aby, bby);
    }
    ll ans = 1e18;
    for (ll px1 : closestLanders(xa, ya, sqSize, true)) {
      for (ll px2 : closestLanders(xb, yb, sqSize, false)) {
        ans = min(
            ans, abs(yb - ya) + abs(px1 - px2) + abs(xa - px1) + abs(xb - px2));
      }
    }
    return ans;
  }
  return abs(xb - xa) + abs(yb - ya);
}
int main() {
  pow3[0] = 1;
  for (int i = 1; i < LOGNMAX; ++i) pow3[i] = pow3[i - 1] * 3;
  int q;
  scanf("%d", &q);
  for (int qta = 0; qta < q; ++qta) {
    ll xa, ya, xb, yb;
    scanf("%lld %lld %lld %lld", &xa, &ya, &xb, &yb);
    printf("%lld\n", solve(xa - 1, ya - 1, xb - 1, yb - 1, pow3[30]));
  }
  return 0;
}
