#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "string"
#include "map"
#include "unordered_map"
#include "unordered_set"
#include "iomanip"
#include "cmath"
#include "random"
#include "bitset"
#include "cstdio"
#include "numeric"
#include "cassert"
#include "ctime"

using namespace std;

//constexpr long long int MOD = 1000000007;
constexpr int MOD = 1000000007;
//constexpr int MOD = 998244353;
//constexpr long long int MOD = 998244353;
constexpr long double EPS = 1e-12;


int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	int K;
	cin >> K;
	vector<long long int>by(32, 1);
	for (int i = 1; i <= 31; i++) {
		by[i] = by[i - 1] * 3;
	}

	/*
	vector<vector<int>>v(27, vector<int>(27));
	for (int i = 1; i <= 8; i += 3) {
		for (int j = 1; j <= 8; j += 3)v[i][j] = 1;
	}
	for (int i = 3; i <= 5; i++) {
		for (int j = 3; j <= 5; j++)v[i][j] = 1;
	}
	for (int i = 0; i < 27; i++) {
		for (int j = 0; j < 27; j++) {
			v[i][j] = v[i % 9][j % 9];
		}
	}
	for (int i = 9; i < 18; i++) {
		for (int j = 9; j < 18; j++)v[i][j] = 1;
	}
	for (auto i : v) {
		for (auto j : i)cout << j;
		cout << endl;
	}
	for (int sy = 0; sy < 27; sy++) {
		for (int sx = 0; sx < 27; sx++) {
			for (int gy = 0; gy < 27; gy++) {
				for (int gx = 0; gx < 27; gx++) {
					if (v[sy][sx] || v[gy][gx])continue;
					vector<vector<int>>dis(27, vector<int>(27, MOD));
					dis[sy][sx] = 0;
					queue<pair<int, int>>Q;
					Q.push({ sy,sx });
					while (!Q.empty()) {
						int ny, nx;
						tie(ny, nx) = Q.front();
						Q.pop();
						int dir[] = { 0,-1,0,1,0 };
						for (int i = 0; i < 4; i++) {
							int y = ny + dir[i];
							int x = nx + dir[i + 1];
							if (y < 0 || y >= 27 || x < 0 || x >= 27)continue;
							if (v[y][x])continue;
							if (dis[y][x] > dis[ny][nx] + 1) {
								dis[y][x] = dis[ny][nx] + 1;
								Q.push({ y,x });
							}
						}
					}
					int a = dis[gy][gx];
					int b = 0;
					long long int ans = abs(sy - gy) + abs(sx - gx);
					int num = -1;
					for (int i = 29; i >= 0; i--) {
						if (abs(sx - gx) < by[i] + 1||(sx+by[i]+by[i+1])/by[i+1]== (gx + by[i]+ by[i + 1]) / by[i + 1])continue;
						for (int j = i; j >= 0; j--) {
							if (sy%by[j + 1] >= by[j] && sy%by[j + 1] < by[j] * 2 && gy%by[j + 1] >= by[j] && gy%by[j + 1] < by[j] * 2 && abs(sy - gy) < by[j]) {
								num = j;
								break;
							}
						}
						if (num >= 0) {
							long long int add = min(sy%by[num + 1] + 1 + gy % by[num + 1] + 1 - by[num] * 2 - abs(sy - gy), by[num] * 2 - sy % by[num + 1] + by[num] * 2 - gy % by[num + 1] - abs(sy - gy));
							b = ans + add;
							break;
						}
					}
					if (num == -1) {
						for (int i = 29; i >= 0; i--) {
							if (abs(sy - gy) < by[i] + 1 || (sy + by[i] + by[i + 1]) / by[i + 1] == (gy + by[i] + by[i + 1]) / by[i + 1])continue;
							for (int j = i; j >= 0; j--) {
								if (sx%by[j + 1] >= by[j] && sx%by[j + 1] < by[j] * 2 && gx%by[j + 1] >= by[j] && gx%by[j + 1] < by[j] * 2 && abs(sx - gx) < by[j]) {
									num = j;
									break;
								}
							}
							if (num >= 0) {
								long long int add = min(sx%by[num + 1] + 1 + gx % by[num + 1] + 1 - by[num] * 2 - abs(sx - gx), by[num] * 2 - sx % by[num + 1] + by[num] * 2 - gx % by[num + 1] - abs(sx - gx));
								b = ans + add;
								break;
							}
						}
						if (num == -1) {
							b = ans;
						}
					}
					if (a != b) {
						cout << sy << " " << sx << " " << gy << " " << gx << endl;
						cout << a << " " << b << endl;
						cout << num << endl;
					}

				}
			}
		}
	}
	return 0;
	*/
	while (K--) {
		long long int sy, sx, gy, gx;
		cin >> sy >> sx >> gy >> gx;
		sy--, sx--, gy--, gx--;
		long long int ans = abs(sy - gy) + abs(sx - gx);
		int num = -1;
		for (int i = 29; i >= 0; i--) {
			if (abs(sx - gx) < by[i] + 1 || (sx + by[i] + by[i + 1]) / by[i + 1] == (gx + by[i] + by[i + 1]) / by[i + 1])continue;
			for (int j = i; j >= 0; j--) {
				if (sy%by[j + 1] >= by[j] && sy%by[j + 1] < by[j] * 2 && gy%by[j + 1] >= by[j] && gy%by[j + 1] < by[j] * 2 && abs(sy - gy) < by[j]) {
					num = j;
					break;
				}
			}
			if (num >= 0) {
				long long int add = min(sy%by[num + 1] + 1 + gy % by[num + 1] + 1 - by[num] * 2 - abs(sy - gy), by[num] * 2 - sy % by[num + 1] + by[num] * 2 - gy % by[num + 1] - abs(sy - gy));
				cout << ans + add << endl;
				break;
			}
		}
		if (num == -1) {
			for (int i = 29; i >= 0; i--) {
				if (abs(sy - gy) < by[i] + 1 || (sy + by[i] + by[i + 1]) / by[i + 1] == (gy + by[i] + by[i + 1]) / by[i + 1])continue;
				for (int j = i; j >= 0; j--) {
					if (sx%by[j + 1] >= by[j] && sx%by[j + 1] < by[j] * 2 && gx%by[j + 1] >= by[j] && gx%by[j + 1] < by[j] * 2 && abs(sx - gx) < by[j]) {
					//	cout << "Num " << num << endl;
						num = j;
					//	cout << "num " << num << endl;
						break;
					}
				}
				if (num >= 0) {
					long long int add = min(sx%by[num + 1] + 1 + gx % by[num + 1] + 1 - by[num] * 2 - abs(sx - gx), by[num] * 2 - sx % by[num + 1] + by[num] * 2 - gx % by[num + 1] - abs(sx - gx));
					cout << ans + add << endl;
					break;
				}
			}
			if (num == -1) {
				cout << ans << endl;
			}
		}
		//cout << num << endl;
	}
}

Measured memory_bytes: 384