#include <bits/stdc++.h>

using namespace std;
using ll = long long;
constexpr int LOGNMAX = 35;

ll pow3[LOGNMAX];

// 1 = right, 0 = both, -1 = left
vector<ll> closestLanders(ll xc, ll yc, ll sqSize, int goalSide, ll offset) {
//	printf("CL %lld %lld %lld %lld\n", xc, yc, sqSize, (ll)goalSide);
	if (sqSize == 1) return {offset, offset};
	ll subRange = sqSize / 3;
	int subX = xc / subRange, subY = yc / subRange;
//	printf("subBlock %d %d\n", subX, subY);
	if (subX == 1) {
		if ((subY == 0 && goalSide != -1) || (subY == 2 && goalSide != 1)) {
			return {subRange - 1 + offset, 2 * subRange + offset};
		} else {
//			printf("ADD OFFSET %lld\n", subRange);
			return closestLanders(xc % subRange, yc % subRange, subRange, goalSide, offset + subRange);
		}
	} else {
//		printf("ADD OFFSET %lld\n", xc / subRange * subRange);
		return closestLanders(xc % subRange, yc % subRange, subRange, (goalSide + 1 == subY ? goalSide : 0),
				offset + (xc / subRange * subRange));
	}
}

ll solve(ll xa, ll ya, ll xb, ll yb, ll sqSize) {
//	printf("solving %lld %lld %lld %lld %lld\n", xa, ya, xb, yb, sqSize);
	if (sqSize == 1) return 0;
	ll subRange = sqSize / 3;
	ll abx = xa / subRange, aby = ya / subRange;
	ll bbx = xb / subRange, bby = yb / subRange;
//	printf("subblocks %lld %lld %lld %lld\n", abx, aby, bbx, bby);
	if (abx == bbx && aby == bby) {
		return solve(xa % subRange, ya % subRange, xb % subRange, yb % subRange, subRange);
	}
	// are they locked in the y=1|y=1 case?
	if (aby == 1 && bby == 1) {
		swap(xa, ya); swap(xb, yb); swap(abx, aby); swap(bbx, bby);
	}
	if (abx == 1 && bbx == 1) {
//		printf("run around hole case %lld %lld %lld %lld\n", xa, ya, xb, yb);
		return abs(yb - ya) + min(xa + xb - 2 * (subRange - 1), 4 * subRange - xa - xb);
	}
	// do they need closestLanders treatment?
	if (abx == bbx || aby == bby) {
		if (aby == bby) {
			swap(xa, ya); swap(xb, yb); swap(abx, aby); swap(bbx, bby);
		}
		if (ya > yb) {
			swap(xa, xb); swap(ya, yb); swap(abx, bbx); swap(aby, bby);
		}
//		printf("solving bridge case %lld %lld %lld %lld %lld\n", xa, ya, xb, yb, sqSize);
		ll ans = 1e18; 
//		printf("using for first side: %d\n", (bby - aby == 2 ? 0 : 1));
		vector<ll> clList1 = closestLanders(xa % subRange, ya % subRange, subRange, (bby - aby == 2 ? 0 : 1), 0);
		vector<ll> clList2 = closestLanders(xb % subRange, yb % subRange, subRange, -1, 0);
		for (ll px1 : clList1) {
			for (ll px2 : clList2) {
//				printf("checking CL pair %lld %lld\n", px1, px2);
				ans = min(ans, abs(yb - ya) + abs(px1 - px2) + abs(xa % subRange - px1) + abs(xb % subRange - px2));
			}
		}
		return ans;
	}
	// default case
	return abs(xb - xa) + abs(yb - ya);	
}

int main() {
	pow3[0] = 1;
	for (int i = 1; i < LOGNMAX; ++i) pow3[i] = pow3[i-1] * 3;
	int q; scanf("%d", &q);
	for (int qta = 0; qta < q; ++qta) {
		ll xa, ya, xb, yb; scanf("%lld %lld %lld %lld", &xa, &ya, &xb, &yb);
		printf("%lld\n", solve(xa - 1, ya - 1, xb - 1, yb - 1, pow3[30]));
	}
	return 0;
}
