#include<bits/stdc++.h>
using namespace std;
int64_t len(int64_t a,int64_t b,int64_t c,int64_t d,int64_t p){
  if(a/p!=c/p&&b/p!=d/p)
    return abs(c-a)+abs(d-b);
  if(a/p==c/p&&b/p==d/p)
    return len(a%p,b%p,c%p,d%p,p/3);
  if(a/p==c/p)
    return len(b,a,d,c,p);
  int64_t xa=a;
  int64_t xc=c;
  int k=0;
  while(abs(xc-xa)>1){
    k++;
    xc/=3;
    xa/=3;
  }
  int64_t x=(b+d)/2;
  vector<int> t;
  while(x>0){
    t.push_back(x%3);
    x/=3;
  }
  int64_t l=0;
  int64_t g=0;
  bool f=0;
  for(int i=(int)t.size()-1;i>=0;i--){
    l*=3;
    g*=3;
    if(f){
      l+=2;
      continue;
    }
    if(i<k&&t.at(i)==1){
      g+=2;
      f=1;
      continue;
    }
    l+=t.at(i);
    g+=t.at(i);
  }
  return min(abs(c-a)+abs(l-b)+abs(l-d),abs(c-a)+abs(g-b)+abs(g-d));
}
int main(){
  int q;
  cin>>q;
  for(int _=0;_<q;_++){
    int64_t a,b,c,d;
    cin>>a>>b>>c>>d;
    a--;
    b--;
    c--;
    d--;
    int64_t p=1;
    while(p<=max({a,b,c,d}))
      p*=3;
    cout<<len(a,b,c,d,p/3)<<endl;
  }
}