/* Generated by powerful Codeforces Tool
 * You can download the binary file in here https://github.com/xalanq/cf-tool (win, osx, linux)
 * Author: step_by_step
 * Time: 2020-03-03 17:35:02
**/

//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize("unroll-loops")
  
#include <iostream>
#include <stdlib.h>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <assert.h>
#include <memory.h>
#include <time.h>
#include <bitset>

#define uint unsigned int
#define ll long long
#define ull unsigned long long
#define ld long double
#define rep(i, l, r) for (int i = (l); i < (r); i++)
#define repb(i, r, l) for (int i = (r); i > (l); i--)
#define sz(a) (int)a.size()
#define fi first
#define se second
#define mp(a, b) make_pair(a, b)
#define rank qwertyuio
#define next dfghjk
#define prev fhsgfhjf
#define plus fsghsf
#define minus ytryr
#define y1 gfvtydvtd
  
using namespace std;
  
inline bool setmin(int &x, int y) { return (y < x) ? x = y, 1 : 0; }
inline bool setmax(int &x, int y) { return (y > x) ? x = y, 1 : 0; }
inline bool setmin(ll &x, ll y) { return (y < x) ? x = y, 1 : 0; }
inline bool setmax(ll &x, ll y) { return (y > x) ? x = y, 1 : 0; }
  
const int N = 100000;
const int inf = (int)1e9 + 1;
const ll big = (ll)1e18 + 1;
const int P = 239;
const int P1 = 31;
const int P2 = 57;
const int MOD = (int)1e9 + 7;
const int MOD1 = (int)1e9 + 9;
const int MOD2 = 998244353;
const ld eps = 1e-9;
const double pi = atan2(0, -1);
const int ABC = 26;

int x1[30], y1[30], x2[30], y2[30];
ll pw[30];

void init() {
    pw[0] = 1;
    rep(i, 1, 30) {
        pw[i] = pw[i - 1] * 3;
    }
}

ll get_val(int len, int *a) {
    ll res = 0;
    rep(i, 0, len) {
        res += a[i] * pw[i];
    }
    return res;
}

void convert(ll v, int *a) {
    rep(i, 0, 30) {
        a[i] = v % 3;
        v /= 3;
    }
}

void rotate_counter(int *x, int *y, int len) {
    rep(i, 0, len) {
        y[i] = (2 - y[i]);
        swap(x[i], y[i]);
    }
}

ll solve(int pos) {
    //cout << pos << endl;
    //cout << x1[pos] << " " << y1[pos] << " " << x2[pos] << " " << y2[pos] << endl;
    if (x1[pos] != x2[pos] && y1[pos] != y2[pos]) {
        return abs(get_val(pos + 1, x1) - get_val(pos + 1, x2)) + 
            abs(get_val(pos + 1, y1) - get_val(pos + 1, y2));
    }
    if (x1[pos] == x2[pos] && y1[pos] == y2[pos]) {
        if (pos == 0) {
            return 0;
        }
        return solve(pos - 1);
    }
    while (true) {
        //cout << x1[pos] << " " << y1[pos] << " " << x2[pos] << " " << y2[pos] << endl;
        if ((y1[pos] == 0 && y2[pos] == 0) || (y1[pos] == 1 && y2[pos] == 1)) {
            break;
        }
        rotate_counter(x1, y1, pos + 1);
        rotate_counter(x2, y2, pos + 1);
    }
    if (x1[pos] > x2[pos]) {
        swap(x1, x2);
        swap(y1, y2);
    }
    //cout << x1[pos] << " " << y1[pos] << " " << x2[pos] << " " << y2[pos] << endl;
    if (y1[pos] == 0) {
        if (pos == 0) {
            return abs(x1[pos] - x2[pos]);
        }
        int p1 = x1[pos] * 3 + x1[pos - 1];
        int p2 = x2[pos] * 3 + x2[pos - 1];
        assert(p1 < p2);
        if (p2 - p1 == 1) {
            if (y1[pos - 1] == y2[pos - 1]) {
                x1[pos - 1] = 0; y1[pos - 1] = 0;
                x2[pos - 1] = 1; y2[pos - 1] = 0;
                return solve(pos - 1);
            } else {
                return abs(get_val(pos + 1, x1) - get_val(pos + 1, x2)) + 
                    abs(get_val(pos + 1, y1) - get_val(pos + 1, y2));
            }
        } else {
            x1[pos - 1] = 0;
            x2[pos - 1] = 2;
            return solve(pos - 1) + ((p2 - p1) - 2) * pw[pos - 1];
        }
    } else {
        //cout << x1[pos - 1] << " " << y1[pos - 1] << " " << x2[pos - 1] << " " << y2[pos - 1] << endl;
        ll v1 = ((pw[pos] - 1) - get_val(pos, x1)) + get_val(pos, y1);
        ll v2 = ((pw[pos] - 1) - get_val(pos, x1)) + ((pw[pos] - 1) - get_val(pos, y1));
        ll v3 = get_val(pos, x2) + get_val(pos, y2);
        ll v4 = get_val(pos, x2) + ((pw[pos] - 1) - get_val(pos, y2));
        //cout << v1 << " " << v2 << " " << v3 << " " << v4 << endl;
        return min(v1 + v3, v2 + v4) + 2 + 1 + pw[pos];
    }
}

int main()
{
    //freopen("a.in", "r", stdin);
    //freopen("a.out", "w", stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.precision(20);
    cout << fixed;
    //ll TL = 10.95 * CLOCKS_PER_SEC;
    //clock_t time = clock();

    init();
    int q;
    cin >> q;
    while (q--) {
        ll a, b, c, d;
        cin >> a >> b >> c >> d;
        a--; b--; c--; d--;
        convert(a, x1);
        convert(b, y1);
        convert(c, x2);
        convert(d, y2);

        cout << solve(29) << "\n";
    }


    /*int x, y;
    cin >> x >> y;
    rep(i, 0, 9) {
        rep(j, 0, 9) {
            if ((i % 3 == 1 && j % 3 == 1) || (i / 3 == 1 && j / 3 == 1)) {
                cout << "xx ";
            } else {
                convert(x, x1);
                convert(y, y1);
                convert(i, x2);
                convert(j, y2);
                int res = solve(29);
                if (res < 10) {
                    cout << " ";
                }
                cout << res << " ";
            }

        }
        cout << "\n";
    }*/
    return 0;
}

Measured memory_bytes: 384