#include <bits/stdc++.h>
using namespace std;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
using Int = long long;
const char newl = '\n';

//INSERT ABOVE HERE
signed main(){
  cin.tie(0);
  ios::sync_with_stdio(0);

  const Int n = 30;
  vector<Int> po(n,1);
  for(Int i=0;i+1<n;i++) po[i+1]=po[i]*3;

  auto solve=[&](Int a,Int b,Int c,Int d)->Int{
    for(Int k=n-1;k>=0;k--){
      Int A=a/po[k];
      Int B=b/po[k];
      Int C=c/po[k];
      Int D=d/po[k];
      if(A==C and A%3==1 and abs(B-D)>=2){
        Int x1=a%po[k];
        Int x2=c%po[k];
        return abs(b-d)+min(x1+1+1+x2,(po[k]-(x1+1))+1+1+(po[k]-(x2+1)));
      }
      if(B==D and B%3==1 and abs(A-C)>=2){
        Int y1=b%po[k];
        Int y2=d%po[k];
        return abs(a-c)+min(y1+1+1+y2,(po[k]-(y1+1))+1+1+(po[k]-(y2+1)));
      }
    }
    return abs(a-c)+abs(b-d);
  };

  Int q;
  cin>>q;

  for(Int i=0;i<q;i++){
    Int a,b,c,d;
    cin>>a>>b>>c>>d;
    a--;b--;c--;d--;
    cout<<solve(a,b,c,d)<<newl;
  }
  return 0;
}
