#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll cost=0;
ll a,b,c,d;
void solve(ll sz)
{
	ll x1=a/sz,y1=b/sz,x2=c/sz,y2=d/sz;
	if(x1!=x2||y1!=y2)
	{
		if(x1==x2&&x1%3==1&&abs(y1-y2)>1)
		{
			cost=min(a%sz+c%sz+2,2*sz-a%sz-c%sz)+abs(d-b);
			return;
		}
		if(y1==y2&&y1%3==1&&abs(x1-x2)>1)
		{
			cost=min(b%sz+d%sz+2,2*sz-b%sz-d%sz)+abs(a-c);
			return;
		}
	}
	if(sz>1)
	{
		solve(sz/3);
	}
}
int main(void)
{
	ll q;
	ll three=1;
	scanf("%lld",&q);
	for(ll i=0;i<30;i++) three*=3;
	while(q--)
	{

		scanf("%lld%lld%lld%lld",&a,&b,&c,&d);
		a--,b--,c--,d--;
		cost=abs(a-c)+abs(b-d);
		solve(three/3);
		printf("%lld\n",cost);
	}
}