#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <set>
#include <map>
#include <vector>
#include <string>

using namespace std;

#define LL long long

const LL dx[4] = {1, -1, 0, 0};
const LL dy[4] = {0, 0, 1, -1};

LL _abs(LL x) {
	if (x > 0) {
		return x;
	}
	return (-x);
}

vector<int> getBit(LL x, int bitn = 35) {
	vector<int> res;
	res.clear();
	while (x > (LL)(0)) {
		res.push_back((int)(x % (LL)(3)));
		x /= (LL)(3);
	}
	while (res.size() < bitn) {
		res.push_back(0);
	}
	return res;
}
int bitn = 35;

LL getDis(LL a, LL b, LL sz) {
	LL down = (a + b + 2);
	LL up = (sz - a) + (sz - b);
	return min(up, down) - _abs(a - b);
}
LL getX(vector<int> x, int k) {
	LL res = 0;
	for (int i = k - 1; i >= 0; --i) {
		res = res * (LL)(3) + (LL)(x[i]);
	}
	return res;
}
LL getM3(int k) {
	LL res = 1;
	for (int i = 0; i < k; ++i) {
		res *= (LL)(3);
	}
	return res;
}

vector<int> cutV(vector<int> &a, int x) {
	vector<int> res;
	res.clear();
	for (int i = 0; i < x; ++i) {
		res.push_back(a[i]);
	}
	return res;
}
LL shortestNextNeighbor(vector<int> x1, vector<int> y1, vector<int> x2, vector<int> y2, bool sameX) {
	int n = x1.size();
	bool diffX = !sameX;
	LL res = 0;
	for (int i = n - 1; i >= 0; --i) {
		if (diffX) {
			if (y1[i] == 1 && y2[i] == 1) {
				LL yy1 = getX(y1, i);
				LL yy2 = getX(y2, i);
				LL sz = getM3(i);
				return getDis(yy1, yy2, sz);
			}
			else if (y1[i] != y2[i]) {
				return res;
			}
		}
		else {
			// cout << "here" << endl;
			if (x1[i] == 1 && x2[i] == 1) {
				LL xx1 = getX(x1, i);
				LL xx2 = getX(x2, i);
				LL sz = getM3(i);
				// printf("xx1 = %lld, xx2 = %lld, sz = %lld\n", xx1, xx2, sz);
				// printf("dis = %lld\n", getDis(xx1, xx2, sz));
				return getDis(xx1, xx2, sz);
			}
			else if (x1[i] != x2[i]) {
				return res;
			}
		}
	}
	return res;
}

LL shortestNeighbor(vector<int> x1, vector<int> y1, vector<int> x2, vector<int> y2, int xx1, int yy1, int xx2, int yy2) {
	int n = x1.size();
	bool noContact = false;
	if (yy1 == yy2) {
		if (xx1 > xx2) {
			swap(y1, y2);
			swap(x1, x2);
		}
		for (int i = n - 1; i >= 0; --i) {
			// cout << "i = " << i << endl;
			if (y1[i] == 1 && y2[i] == 1 && (noContact || (x1[i] < 1 || x2[i] > 1))) {
				LL yy1 = getX(y1, i);
				LL yy2 = getX(y2, i);
				LL sz = getM3(i);
				// cout << "stop at i = " << i << endl;
				return getDis(yy1, yy2, sz);
			}
			else if (y1[i] != y2[i]) {
				return 0;
			}
			else if (x1[i] <= 1 || x2[i] >= 1) {
				noContact = true;
			}
		}
	}
	if (xx1 == xx2) {
		if (yy1 > yy2) {
			swap(x1, x2);
			swap(y1, y2);
		}
		for (int i = n - 1; i >= 0; --i) {
			if (x1[i] == 1 && x2[i] == 1 && (noContact || (y1[i] < 1 || y2[i] > 1))) {
				LL xx1 = getX(x1, i);
				LL xx2 = getX(x2, i);
				LL sz = getM3(i);
				// printf("xx1 = %lld, xx2 = %lld, sz = %lld\n", xx1, xx2, sz);
				// printf("dis = %lld\n", getDis(xx1, xx2, sz));
				return getDis(xx1, xx2, sz);
			}
			else if (x1[i] != x2[i]) {
				return 0;
			}
			else if (y1[i] <= 1 || y2[i] >= 1) {
				noContact = true;
			}
		}
	}
	return 0;
}

void printVector(vector<int> x) {
	for (int i = 0; i < x.size(); ++i) {
		cout << x[i];
	}
	cout << endl;
}

LL getPath(LL x1, LL y1, LL x2, LL y2) {
	vector<int> xb1 = getBit(x1), xb2 = getBit(x2);
	vector<int> yb1 = getBit(y1), yb2 = getBit(y2);

	// cout << "x1 = ";
	// printVector(xb1);
	// cout << "x2 = ";
	// printVector(xb2);
	// cout << "y1 = ";
	// printVector(yb1);
	// cout << "y2 = ";
	// printVector(yb2);

	LL res = _abs(x1 - x2) + _abs(y1 - y2);
	for (int i = bitn - 1; i >= 0; --i) {
		if (xb1[i] == xb2[i] && yb1[i] == yb2[i]) {
			continue;
		}
		int xx1 = xb1[i], xx2 = xb2[i];
		int yy1 = yb1[i], yy2 = yb2[i];
		// printf("(%d, %d), (%d, %d)\n", xx1, yy1, xx2, yy2);

		bool corner1 = true;
		/* if (xx1 == 0 && yy1 == 1) {
			corner1 = false;
		}
		if (xx1 == 2 && yy1 == 1) {
			corner1 = false;
		}
		if (xx1 == 1 && yy1 == 0) {
			corner1 = false;
		}
		if (xx1 == 1 && yy1 == 2) {
			corner1 = false;
		} */
		corner1 = (((xx1 + yy1) % 2) == 0);


		//LL zero = (LL)(0), one = (LL)(1), two = (LL)(2);
		if (corner1) {
			if (xx2 != xx1 && yy2 != yy1) {
				return res;
			}
			else {
				int diff = abs(xx1 - xx2) + abs(yy1 - yy2);
				if (diff == 2) {
				// cout << "here" << endl;
					return res + shortestNextNeighbor(cutV(xb1, i), cutV(yb1, i), cutV(xb2, i), cutV(yb2, i), (xx1 == xx2));
				}
				else {
					return res + shortestNeighbor(cutV(xb1, i), cutV(yb1, i), cutV(xb2, i), cutV(yb2, i), xx1, yy1, xx2, yy2);
				}
				// continue;
			}
		}
		else {
			int diff = _abs(xx1 - xx2) + _abs(yy1 - yy2);
			if (diff == 1) {
				// cout << "here" << endl;
				return res + shortestNeighbor(cutV(xb1, i), cutV(yb1, i), cutV(xb2, i), cutV(yb2, i), xx1, yy1, xx2, yy2);
				// continue;
			}
			else {
				// return res;
				if (xx2 == xx1 && yy2 + yy1 == 2 && xx1 == 1) {
					LL sz = getM3(i);
					LL xz1 = getX(xb1, i), xz2 = getX(xb2, i);
					return res + getDis(xz1, xz2, sz);
				}
				if (yy2 == yy1 && xx2 + xx1 == 2 && yy1 == 1) {
					LL sz = getM3(i);
					LL yz1 = getX(yb1, i), yz2 = getX(yb2, i);
					return res + getDis(yz1, yz2, sz);
				}
				return res;
			}
		}
	}
	return res;
}
int q;
LL a, b, c, d;
int main() {
	cin >> q;
	for (int i = 0; i < q; ++i) {
		cin >> a >> b >> c >> d;
		a -= (LL)(1); b -= (LL)(1); c -= (LL)(1); d -= (LL)(1);
		cout << getPath(a, b, c, d) << endl;
	}
	return 0;
}

Measured memory_bytes: 384