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

typedef long long ll;
#define REP(i,n) for(int i=0,_n=(int)(n);i<_n;++i)
#define ALL(v) (v).begin(),(v).end()
#define CLR(t,v) memset(t,(v),sizeof(t))
template<class T1,class T2>ostream& operator<<(ostream& os,const pair<T1,T2>&a){return os<<"("<<a.first<<","<<a.second<< ")";}
template<class T>void pv(T a,T b){for(T i=a;i!=b;++i)cout<<(*i)<<" ";cout<<endl;}
template<class T>void chmin(T&a,const T&b){if(a>b)a=b;}
template<class T>void chmax(T&a,const T&b){if(a<b)a=b;}

ll three[40];

using P = pair<ll, ll>;

ll solve2(int K, ll a, ll b, ll c, ll d) {
  if (a == c && b == d) return 0;
  const ll L = three[K-1];
  vector<ll> ps({0, L-1, 2*L, 3*L-1});
  vector<P> checkpoints;
  for (ll r : ps) {
    for (ll c : ps) {
      checkpoints.push_back({r, c});
    }
  }
  // pv(ALL(checkpoints));
  // cout <<  K << " " << a << " " << b << " " << c << " " << d << endl;
  ll ans = 1LL << 61;
  for (P p : checkpoints) {
    ll cur = 0;
    cur += abs(a - p.first) + abs(b - p.second);
    cur += abs(c - p.first) + abs(d - p.second);
    chmin(ans, cur);
  }
  return ans;
}

ll solve(int K, ll a, ll b, ll c, ll d) {
  if (a == c && b == d) return 0;
  ll L = three[K-1];

  bool same_row = a / L == c / L;
  bool same_col = b / L == d / L;
  if (same_row && same_col) {
    return solve(K-1, a % L, b % L, c % L, d % L);
  }
  if (!same_row && !same_col) { return solve2(K, a, b, c, d); }
  if (same_row && a/L == 1) { return solve2(K, a, b, c, d); }
  if (same_col && b/L == 1) { return solve2(K, a, b, c, d); }

  if (!same_row) {
    swap(a, b);
    swap(c, d);
    same_row = !same_row;
    same_col = !same_col;
  }

  while (L > 1) {
    L /= 3;
    if (a / L != c / L) {
      return abs(a - c) + abs(b - d);
    }
    if (abs(b/L - d/L) >= 2 && a / L == c / L && (a / L) % 3 == 1) break;
  }

  if (L == 1) {
    if (a != c) return abs(a-c) + abs(b-d);
    if (a % 3 != 1) return abs(a-c) + abs(b-d);
    if (abs(b-d) <= 1) return abs(a-c) + abs(b-d);
    return abs(b-d) + 2;
  } else {
    a %= L;
    c %= L;
    return abs(b-d) + min(a+c+2, L-a+L-c);
  }
}


int main2() {

  int Q; cin >> Q;
  while (Q--) {
    ll a, b, c, d;
    cin >> a >> b >> c >> d;
    ll ans = solve(31, a-1, b-1, c-1, d-1);
    cout << ans << endl;
  }
  return 0;
}

int main() {

  three[0] = 1;
  for (int i = 1; i < 40; i++) three[i] = three[i-1] * 3;

#ifdef LOCAL
  for (;!cin.eof();cin>>ws)
#endif
    main2();
  return 0;
}