#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <climits>
#include <cstring>
#include <cassert>

#define rep(i, m, n) for(int i=int(m);i<int(n);i++)
#define all(c) begin(c),end(c)

template<typename T1, typename T2>
inline void chmin(T1 &a, T2 b) { if (a > b) a = b; }

template<typename T1, typename T2>
inline void chmax(T1 &a, T2 b) { if (a < b) a = b; }

typedef long long int ll;
using ll = long long int;
using ull = long long unsigned int;
using Int = long long int;
using Double = long double;
using namespace std;
#define INF (1 << 30) - 1
#define INFl (ll)5e15
#define DEBUG 0
#define dump(x)  cerr << #x << " = " << (x) << endl
#define MOD 1000000007


//edit


//template<typename T>
Int pow(Int n, Int k) {
    Int ret = 1;
    while (k--) ret *= n;
    return ret;
}

//template<typename T>
//T abs(T a) {
//    if (a < 0) return -a;
//    return a;
//}

class Solve {
public:


    Int dist(Int x1, Int y1, Int x2, Int y2) {
        return abs(x1 - x2) + abs(y1 - y2);
    }

    // 3^l x 3^kの正方形を考える
    Int rec2(Int l, Int k, Int x1, Int y1, Int x2, Int y2) {
//        if (l == 0) {
//
//        }
        Int br = pow(3ll, l - 1);
        Int r1 = x1 / br, c1 = y1 / br;
        Int r2 = x2 / br, c2 = y2 / br;

        if (r1 != r2) {
            Int ret = abs(x1 - x2) + abs(y1 - y2);
            return ret;
        }

        if (r1 == 1 && abs(c1 - c2) >= 2) {
            Int p = pow(3ll, l - 1) - 1;
            Int q = pow(3ll, l - 1) * 2;
//            Int alpha = min(abs(p - x1) + abs(p - x2), abs(q - x1) + abs(q - x2));
            Int alpha = 2ll * min(min(abs(p - x1), abs(p - x2)), min(abs(q - x1), abs(q - x2)));
            Int ret = dist(x1, y1, x2, y2) + alpha;
            return ret;
        }

        if (l == 1) {
            Int ret = dist(x1, y1, x2, y2);
            if (r1 == 1 && abs(c1 - c2) >= 2) {
                ret += 2;
            }
            return ret;
        }

        Int ret = rec2(l - 1, k, x1 % br, y1, x2 % br, y2);
        return ret;
    }

    Int rec(Int k, Int x1, Int y1, Int x2, Int y2) {
        Int br = pow(3ll, k - 1); //それぞれの区画の大きさ

        Int r1 = x1 / br, c1 = y1 / br;
        Int r2 = x2 / br, c2 = y2 / br;

        if (r1 == r2 && c1 == c2) {
            Int ret = rec(k - 1, x1 % br, y1 % br, x2 % br, y2 % br);
            return ret;
        } else if (r1 != r2 && c1 != c2) {
            Int ret = dist(x1, y1, x2, y2);
            return ret;
        } else {
            if (c1 == c2) {
                Int ret = rec(k, y1, x1, y2, x2);
                return ret;
            }

            if (r1 == 1) {
                Int p = pow(3ll, k - 1) - 1;
                Int q = pow(3ll, k - 1) * 2;
//                Int alpha = min(abs(p - x1) + abs(p - x2), abs(q - x1) + abs(q - x2));
                Int alpha = 2ll * min(min(abs(p - x1), abs(p - x2)), min(abs(q - x1), abs(q - x2)));
                Int ret = dist(x1, y1, x2, y2) + alpha;
                return ret;
            }

            if (k == 1) {
                Int ret = dist(x1, y1, x2, y2);
//                if (r1 == 1 && abs(c1 - c2) >= 2) {
//                    ret += 2;
//                }
                return ret;
            }

            Int ret = rec2(k - 1, k, x1 % br, y1, x2 % br, y2);
            return ret;
        }


    }

    void solve() {
        Int Q;
        cin >> Q;
        while (Q--) {
            Int a, b, c, d;
            cin >> a >> b >> c >> d;
            a--, b--, c--, d--;
            Int ans = rec(30, a, b, c, d);
            cout << ans << endl;
        }
    }
};

class Tester {
public:
    Int sz;
    vector<vector<Int>> field;
    vector<vector<vector<vector<Int>>>> dist;

    Tester(Int k) {
        sz = pow(3ll, k);
        field.resize(sz, vector<Int>(sz, 0));
        dist.resize(sz, vector<vector<vector<Int>>>(sz, vector<vector<Int>>(sz, vector<Int>(sz, INFl))));
        rec(k, 0, 0);
        for (int ix = 0; ix < sz; ++ix) {
            for (int iy = 0; iy < sz; ++iy) {
                for (int jx = 0; jx < sz; ++jx) {
                    for (int jy = 0; jy < sz; ++jy) {
                        if (is_floor(ix, iy) && is_floor(jx, jy) && Solve().dist(ix, iy, jx, jy) == 1) {
                            dist[ix][iy][jx][jy] = 1;
                            dist[jx][jy][ix][iy] = 1;
                        }
                    }
                }
            }
        }

        for (int kx = 0; kx < sz; ++kx) {
            for (int ky = 0; ky < sz; ++ky) {
                for (int ix = 0; ix < sz; ++ix) {
                    for (int iy = 0; iy < sz; ++iy) {
                        for (int jx = 0; jx < sz; ++jx) {
                            for (int jy = 0; jy < sz; ++jy) {
//                                if (is_floor(ix, iy) && is_floor(jx, jy)) {
//                                    dist[ix][iy][jx][jy] = 1;
//                                    dist[jx][jy][ix][iy] = 1;
//                                }
                                chmin(dist[ix][iy][jx][jy], dist[ix][iy][kx][ky] + dist[kx][ky][jx][jy]);
                            }
                        }
                    }
                }
            }
        }
    }

    bool is_floor(int x, int y) {
        return !field[x][y];
    }

    // sx, syから始まり、3 ^ k の正方形で色塗り
    void rec(Int k, Int sx, Int sy) {
        if (k == 0) return;

        Int br = pow(3ll, k - 1);
        for (int r = 0; r < 3; ++r) {
            for (int c = 0; c < 3; ++c) {
                if (r == 1 && c == 1) {
                    for (int i = 0; i < br; ++i) {
                        for (int j = 0; j < br; ++j) {
                            field[br + sx + i][br + sy + j] = 1;
                        }
                    }
                } else {
                    rec(k - 1, sx + r * br, sy + c * br);
                }
            }
        }
    }

    void print_field() {
        for (auto line : field) {
            for (auto e : line) {
                if (e == 0) cout << '.';
                else cout << '#';
            }
            cout << endl;
        }
    }

    bool test() {
        Int a = rand() % sz, b = rand() % sz, c = rand() % sz, d = rand() % sz;

        while (!is_floor(a, b)) {
            a = rand() % sz;
            b = rand() % sz;
        }

        while (!is_floor(c, d) || (a == c && b == d)) {
            c = rand() % sz;
            d = rand() % sz;
        }

        cout << a << " " << b << " " << c << " " << d << endl;

        Int ans = Solve().rec(30, a, b, c, d);
        Int bf = dist[a][b][c][d];

        cout << ans << " " << bf << endl;
        cout << endl;

        return ans == bf;
    }

};


int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);

//    pow(3,5)
//    for (int i = 0; i < 60; ++i) {
//        cout << pow(2ll, (Int) i) << endl;
//    }



    bool debug = true;
    debug = false;
    if (debug) {
        Tester tester(3);
//        Int Q;
//        cin >> Q;
//        while (Q--) {
//
//            Int a, b, c, d;
//            cin >> a >> b >> c >> d;
//            a--, b--, c--, d--;
//
//            Int ans = Solve().rec(30, a, b, c, d);
//
//            Int bf = tester.dist[a][b][c][d];
//
//            cout << ans << " " << bf << endl;
//        }

        while (tester.test());


        return 0;
    }


    Solve().solve();


    return 0;
}


Measured memory_bytes: 384