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

//////////////////////////////   Begin Macros

#define ALL(x) (x).begin(), (x).end()
#define rep(i, N) for (int i = 0; i < N; i++)
#define rep1(i, N) for (int i = 1; i <= N; i++)

using ll = long long int;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

template <typename T>
bool chmax(T &m, const T q)
{
  if (m < q)
  {
    m = q;
    return true;
  }
  else
    return false;
}
template <typename T>
bool chmin(T &m, const T q)
{
  if (m > q)
  {
    m = q;
    return true;
  }
  else
    return false;
}
template <typename T1, typename T2>
pair<T1, T2> operator+(const pair<T1, T2> &l, const pair<T1, T2> &r) { return {l.first + r.first, l.second + r.second}; }
template <typename T1, typename T2>
pair<T1, T2> operator-(const pair<T1, T2> &l, const pair<T1, T2> &r) { return {l.first - r.first, l.second - r.second}; }
template <typename T>
pair<T, T> operator*(const pair<T, T> &l, const T &r) { return {l.first * r, l.second * r}; }
template <typename T>
pair<T, T> operator/(const pair<T, T> &l, const T &r) { return {l.first / r, l.second / r}; }
template <typename T>
istream &operator>>(istream &is, vector<T> &vec)
{
  for (auto &v : vec)
    is >> v;
  return is;
}
template <typename T>
ostream &operator<<(ostream &os, const vector<T> &vec)
{
  os << "[";
  for (auto v : vec)
    os << v << ",";
  os << "]";
  return os;
}
template <typename T>
ostream &operator<<(ostream &os, const deque<T> &vec)
{
  os << "deq[";
  for (auto v : vec)
    os << v << ",";
  os << "]";
  return os;
}
template <typename T>
ostream &operator<<(ostream &os, const set<T> &vec)
{
  os << "{";
  for (auto v : vec)
    os << v << ",";
  os << "}";
  return os;
}
template <typename T>
ostream &operator<<(ostream &os, const unordered_set<T> &vec)
{
  os << "{";
  for (auto v : vec)
    os << v << ",";
  os << "}";
  return os;
}
template <typename T>
ostream &operator<<(ostream &os, const multiset<T> &vec)
{
  os << "{";
  for (auto v : vec)
    os << v << ",";
  os << "}";
  return os;
}
template <typename T>
ostream &operator<<(ostream &os, const unordered_multiset<T> &vec)
{
  os << "{";
  for (auto v : vec)
    os << v << ",";
  os << "}";
  return os;
}
template <typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &pa)
{
  os << "(" << pa.first << "," << pa.second << ")";
  return os;
}
template <typename TK, typename TV>
ostream &operator<<(ostream &os, const map<TK, TV> &mp)
{
  os << "{";
  for (auto v : mp)
    os << v.first << "=>" << v.second << ",";
  os << "}";
  return os;
}
template <typename TK, typename TV>
ostream &operator<<(ostream &os, const unordered_map<TK, TV> &mp)
{
  os << "{";
  for (auto v : mp)
    os << v.first << "=>" << v.second << ",";
  os << "}";
  return os;
}

template <typename T>
void reset(vector<T> &v, const T reset_to)
{
  for (auto &x : v)
    x = reset_to;
}
inline int popcount(const unsigned int x) { return __builtin_popcount(x); }
#define dbg(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ") " << __FILE__ << endl;

const int intinf = numeric_limits<int>::max();
#define MOD 1000000007
const pii udlr[4] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

//////////////////////////////   End Macros

ll L1norm(pll xy)
{
  return abs(xy.first) + abs(xy.second);
}

ll dist(pll ab, pll cd, pii level)
{
  if (level.first == 0)
    return abs(ab.second - cd.second);

  ll pow_three_x = pow(3, level.first - 1);

  int A = ab.first / pow_three_x;
  int C = cd.first / pow_three_x;

  if (A != C)
    return L1norm(ab - cd);

  ab.first -= A * pow_three_x;
  cd.first -= A * pow_three_x;
  level.first--;

  if (A != 1)
    return dist(ab, cd, level);

  // A==C==1
  ll B = (ab.second + pow_three_x) / pow_three_x / 3;
  ll D = (cd.second + pow_three_x) / pow_three_x / 3;
  if (B == D)
    return dist(ab, cd, level);

  ll dx = min(abs(ab.first - (-1)) + abs(cd.first - (-1)), abs(ab.first - pow_three_x) + abs(cd.first - pow_three_x));
  ll dy = abs(ab.second - cd.second);
  return dx + dy;
}

void solve()
{
  int Q;
  cin >> Q;
  rep(q, Q)
  {
    ll a, b, c, d;
    cin >> a >> b >> c >> d;
    a--;
    b--;
    c--;
    d--;

    const pii level_init = {30, 30};
    ll ans = max(dist({a, b}, {c, d}, level_init), dist({b, a}, {d, c}, level_init));
    cout << ans << endl;
  }
}

const int maxlevel = 7;
const int size_fractal = pow(3, maxlevel);
vector<vector<bool>> fractal(size_fractal, vector<bool>(size_fractal, false));

void make_fractal(int x, int y, int level)
{
  if (level == 0)
  {
    fractal[x][y] = false;
    return;
  }

  ll pow_three = pow(3, level - 1);

  rep(i, 3) rep(j, 3)
  {
    if (i == 1 and j == 1)
    {
      rep(ii, pow_three) rep(jj, pow_three)
          fractal[x + pow_three + ii][y + pow_three + jj] = true;
      continue;
    }

    make_fractal(x + i * pow_three, y + j * pow_three, level - 1);
  }
}

ll distTest(pll ab, pll cd)
{
  ll ans = 0;

  vector<vector<bool>> is_reached(size_fractal, vector<bool>(size_fractal, false));
  queue<pll> q;
  q.push(ab);
  is_reached[ab.first][ab.second] = true;
  while (!is_reached[cd.first][cd.second])
  {
    queue<pll> nextq;
    while (!q.empty())
    {
      pll xy = q.front();
      q.pop();
      rep(k, 4)
      {
        int nx = xy.first + udlr[k].first;
        int ny = xy.second + udlr[k].second;
        if (!(0 <= nx and nx < size_fractal and 0 <= ny and ny < size_fractal))
          continue;

        if (!fractal[nx][ny] and !is_reached[nx][ny])
        {
          nextq.push({nx, ny});
          is_reached[nx][ny] = true;
        }
      }
    }
    q = nextq;
    ans++;
  }

  return ans;
}

void test()
{
  make_fractal(0, 0, maxlevel);
  int cnt = 0;
  while (cnt < 100)
  {
    // rep(i, size_fractal) cout << i << fractal[i] << endl;
    ll a, b, c, d;
    a = b = c = d = 1;
    // cin >> a >> b >> c >> d;
    while (fractal[a][b] or fractal[c][d])
    {
      a = rand() % size_fractal;
      b = rand() % size_fractal;
      c = rand() % size_fractal;
      d = rand() % size_fractal;
    }
    ll dTest = distTest({a, b}, {c, d});
    ll dAns = max(dist({a, b}, {c, d}, {maxlevel, maxlevel}), dist({b, a}, {d, c}, {maxlevel, maxlevel}));
    if (dAns != dTest)
    {
      cout << "Hack" << endl;
      cout << a << " " << b << " " << c << " " << d << endl;
      cout << "distTest: " << dTest << endl;
      cout << "distAns: " << dAns << endl;
      cin.ignore();
    }
    cnt++;
  }
  cout << "OK" << endl;
}

int main()
{
  solve();

  return 0;
}


Measured memory_bytes: 1024