#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
#define x first
#define y second

#ifdef LOCAL
#include "debug.h"
#endif

const int N = 31;

ll p[N];

int main() {
	#ifdef LOCAL
	freopen("in", "r", stdin);
	freopen("out", "w", stdout);
	#endif

	p[0] = 1;
	for (int i = 1; i < N; i++) p[i] = p[i - 1] * 3LL;

	int q;
	cin >> q;

	while (q--) {
		ll x1, y1, x2, y2;
		scanf("%lld %lld %lld %lld", &x1, &y1, &x2, &y2);
		x1--, y1--, x2--, y2--;

		int at_level = 30;
		ll ans;
		while (true) {
			if (at_level == 0) {
				ans = abs(x1 - x2) + abs(y1 - y2);
				break;
			}

			ll row1 = x1 / p[at_level - 1];
			ll col1 = y1 / p[at_level - 1];
			ll row2 = x2 / p[at_level - 1];
			ll col2 = y2 / p[at_level - 1];

			if (row1 != row2 && col1 != col2) {
				ans = abs(x1 - x2) + abs(y1 - y2);
				break;
			}
			if (row1 == row2 && col1 == col2) {
				at_level--;
				continue;
			}

			if (row1 == row2 && row1 % 3 == 1 && abs(col1 - col2) > 1) {
				ans = abs(y1 - y2);
				ll rem_sum = x1 % p[at_level - 1] + x2 % p[at_level - 1];
				ll down = rem_sum + 2;
				ll up = 2LL * p[at_level - 1] - rem_sum;
				ans += min(down, up);
				break;
			}
			if (col1 == col2 && col1 % 3 == 1 && abs(row1 - row2) > 1) {
				ans = abs(x1 - x2);
				ll rem_sum = y1 % p[at_level - 1] + y2 % p[at_level - 1];
				ll down = rem_sum + 2;
				ll up = 2LL * p[at_level - 1] - rem_sum;
				ans += min(down, up);
				break;
			}

			at_level--;
		}

		printf("%lld\n", ans);
	}

	return 0;
}