#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i,n)for((i)=0;(i)<(int)(n);(i)++)
#define _abs(x) ((x)>0?(x):-(x))
bool between(ll x,ll y1,ll y2){
  if(y1>y2)swap(y1,y2);
  y1++;y2--;
  if(!(y1<=y2))return false;
  while(x> 0){
    if(x% 3 == 1){
      if(y2-y1> 3)return true;
      for(ll y=y1;y<=y2;y++)if(y% 3 == 1)return true;
    }
    x/= 3;y1/= 3;y2/= 3;
  }
  return false;
}
ll get_extra(ll x1,ll y1,ll x2,ll y2){
  ll ans= 0;int i;ll three= 1;
  REP(i,35){
    if(x1/three==x2/three&&between(x1/three,y1/three,y2/three)){
      ll tmp=min(min(x1%three,x2%three) + 1,three-max(x1%three,x2%three));
      ans=max(ans,tmp);
    }
    three*= 3;
  }
  return ans;
}
ll get_dist(ll x1,ll y1,ll x2,ll 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;
  cin >> Q;
  for(int i=0; i<Q; ++i){
    ll a, b, c, d;
    cin>>a>>b>>c>>d;
    --a;--b;--c;--d;
    cout<< get_dist(a,b,c,d) << endl;
  }
}