#include <bits/stdc++.h>
using namespace std;

int main() {
  vector<int64_t> p(31);
  p.at(0) = 1;
  for (int i = 1; i <= 30; i++) {
    p.at(i) = 3 * p.at(i - 1);
  }
  int q;
  cin >> q;
  vector<int64_t> a(q), b(q), c(q), d(q);
  for (int i = 0; i < q; i++) {
    cin >> a.at(i) >> b.at(i) >> c.at(i) >> d.at(i);
  }
  for (int i = 0; i < q; i++) {
    int64_t dh = abs(a.at(i) - c.at(i)), dw = abs(b.at(i) - d.at(i));
    int64_t direct = dh + dw;
    vector<int> a3(30), b3(30), c3(30), d3(30);
    a.at(i)--; b.at(i)--; c.at(i)--; d.at(i)--;
    vector<int64_t> ac = a, bc = b, cc = c, dc = d;
    for (int j = 0; j < 30; j++) {
      a3.at(j) = ac.at(i) % 3;
      ac.at(i) /= 3;
    }
    for (int j = 0; j < 30; j++) {
      b3.at(j) = bc.at(i) % 3;
      bc.at(i) /= 3;
    }
    for (int j = 0; j < 30; j++) {
      c3.at(j) = cc.at(i) % 3;
      cc.at(i) /= 3;
    }
    for (int j = 0; j < 30; j++) {
      d3.at(j) = dc.at(i) % 3;
      dc.at(i) /= 3;
    }
    int64_t add_h = 0, add_w = 0;
    bool same_h = true, same_w = true;
    for (int j = 29; j >= 0; j--) {
      if (add_h == 0 && same_h && a3.at(j) == 1 && c3.at(j) == 1
          && ((same_w && dw >= p.at(j)) || dw >= 2 * p.at(j))) {
        int64_t ar = a.at(i) % p.at(j), cr = c.at(i) % p.at(j);
        add_h = 2 * min({ar + 1, p.at(j) - ar,
                         cr + 1, p.at(j) - cr});
      }
      if (add_w == 0 && same_w && b3.at(j) == 1 && d3.at(j) == 1
          && ((same_h && dh >= p.at(j)) || dh >= 2 * p.at(j))) {
        int64_t br = b.at(i) % p.at(j), dr = d.at(i) % p.at(j);
        add_w = 2 * min({br + 1, p.at(j) - br,
                         dr + 1, p.at(j) - dr});
      }
      if (a3.at(j) != c3.at(j)) same_h = false;
      if (b3.at(j) != d3.at(j)) same_w = false;
    }
    cout << direct + add_h + add_w << endl;
  }
}
