#include <iostream>
using namespace std;

bool between(long long x, long long y1, long long y2) {
  if (y1 > y2) swap(y1, y2);
  y1++, y2--;
  if (y1 > y2) return false;

  while (x) {
    if (x % 3 == 1) {
      if (y2 - y1 > 3) return true;
      for (long long y = y1; y <= y2; y++)
        if (y % 3 == 1) return true;
    }

    x /= 3, y1 /= 3, y2 /= 3;
  }

  return false;
}

long long get_extra(long long x1, long long y1, long long x2, long long y2) {
  long long ans = 0, three = 1;
  for (int i = 0; i < 35; i++) {
    if (x1 / three == x2 / three && between(x1 / three, y1 / three, y2 / three)) {
      long long t = min(min(x1 % three, x2 % three) + 1, three - max(x1 % three, x2 % three));
      ans = max(ans, t);
    }

    three *= 3;
  }

  return ans;
}

long long get_dist(long long x1, long long y1, long long x2, long long y2) {
  return abs(x1 - x2) + abs(y1 - y2) + 2 * max(get_extra(x1, y1, x2, y2), get_extra(y1, x1, y2, x2));
}

int main() {
  int q;
  scanf("%d", &q);
  while (q--) {
    long long a, b, c, d;
    scanf("%lld %lld %lld %lld", &a, &b, &c, &d);

    printf("%lld\n", get_dist(a - 1, b - 1, c - 1, d - 1));
  }

  return 0;
}