#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<ctime>
#include<map>
#include<bitset>
#include<set>
#include<assert.h>
#include<chrono>
#include<random>
#define LL long long
#define mp(x,y) make_pair(x,y)
#define pll pair<long long,long long>
#define pii pair<int,int>
#define SZ(x) ((int)x.size())
using namespace std;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
inline LL read()
{
	LL f=1,x=0;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int stack[20];
template<typename T>inline void write(T x)
{
	if(x<0){putchar('-');x=-x;}
    if(!x){putchar('0');return;}
    int top=0;
    while(x)stack[++top]=x%10,x/=10;
    while(top)putchar(stack[top--]+'0');
}
template<typename T>inline void pr1(T x){write(x);putchar(' ');}
template<typename T>inline void pr2(T x){write(x);putchar('\n');}
template<typename T>inline void chkmin(T &x,T y){x=x<y?x:y;}
template<typename T>inline void chkmax(T &x,T y){x=x>y?x:y;}
LL Rmax;
LL x,y,a,b;
bool in(LL x,LL y,LL z){return x<=z&&z<=y;}
LL getval(LL upx,LL upy,LL downx,LL downy,int opt)
{
	LL L=(opt?(downy-upy+1):(downx-upx+1));
	if(L==1)
	{
		LL ad=0;
		if(opt&&downy%3==2)ad=(abs(y-b)<=1)?0:2;
		if(!opt&&downx%3==2)ad=(abs(x-a)<=1)?0:2;
		return abs(x-a)+abs(y-b)+ad;
	}
	LL xp1=upx+L/3-1,xp2=upx+L/3*2-1,xp3=downx;
	LL yp1=upy+L/3-1,yp2=upy+L/3*2-1,up3=downy;
	
	if(!opt)
	{
		LL p1=!in(upx,xp1,x)?!in(xp1+1,xp2,x)?2:1:0,p2=!in(upx,xp1,a)?!in(xp1+1,xp2,a)?2:1:0;
		if(p1!=p2)return abs(x-a)+abs(y-b);
		else if(p1==1)
		{
			LL q1=(y-1)/(L/3),q2=(b-1)/(L/3);
			if(abs(q2-q1)-1>=1)return min(x-xp1+a-xp1,xp2+1-x+xp2+1-a)+abs(y-b);
			else return getval(upx+p1*(L/3),upy,downx-(2-p1)*(L/3),downy,0);
		}
		else return getval(upx+p1*(L/3),upy,downx-(2-p1)*(L/3),downy,0);
	}
	else
	{
		LL p1=!in(upy,yp1,y)?!in(yp1+1,yp2,y)?2:1:0,p2=!in(upy,yp1,b)?!in(yp1+1,yp2,b)?2:1:0;
		if(p1!=p2)return abs(x-a)+abs(y-b);
		else if(p1==1)
		{
			LL q1=(x-1)/(L/3),q2=(a-1)/(L/3);
			if(abs(q2-q1)-1>=1)return min(y-yp1+b-yp1,yp2+1-y+yp2+1-b)+abs(x-a);
			else return getval(upx,upy+p1*(L/3),downx,downy-(2-p1)*(L/3),1);
		}
		else return getval(upx,upy+p1*(L/3),downx,downy-(2-p1)*(L/3),1);
	}
}
LL solve(LL upx,LL upy,LL downx,LL downy)
{
	LL L=(downx-upx+1);
	LL xp1=upx+L/3-1,xp2=upx+L/3*2-1,xp3=downx;
	LL yp1=upy+L/3-1,yp2=upy+L/3*2-1,yp3=downy;
	
	LL p1=!in(upx,xp1,x)?!in(xp1+1,xp2,x)?2:1:0,p2=!in(upy,yp1,y)?!in(yp1+1,yp2,y)?2:1:0;
	LL q1=!in(upx,xp1,a)?!in(xp1+1,xp2,a)?2:1:0,q2=!in(upy,yp1,b)?!in(yp1+1,yp2,b)?2:1:0;
	if(p1==q1&&p2==q2)return solve(upx+p1*(L/3),upy+p2*(L/3),downx-(2-p1)*(L/3),downy-(2-p2)*(L/3));
	else
	{
		if(p1!=q1&&p2!=q2)return abs(x-a)+abs(y-b);
		if(p1==q1)
		{
			if(p1==1)return min(x-xp1+a-xp1,xp2+1-x+xp2+1-a)+abs(y-b);
			return getval(upx+p1*(L/3),upy,downx-(2-p1)*(L/3),downy,0);
		}
		else
		{
			if(p2==1)return min(y-yp1+b-yp1,yp2+1-y+yp2+1-b)+abs(x-a);
			return getval(upx,upy+p2*(L/3),downx,downy-(2-p2)*(L/3),1);
		}
	}
}
int main()
{
//	freopen("a.in","r",stdin);
//	freopen("a.out","w",stdout); 
	Rmax=1;for(int i=1;i<=30;i++)Rmax=Rmax*3;
//	Rmax=27;
	int T=read();while(T--)
	{
		x=read(),y=read(),a=read(),b=read();
		pr2(solve(1,1,Rmax,Rmax));
	}
	return 0;
}



Measured memory_bytes: 384