#include<bits/stdc++.h>

int main(){
    using namespace std;
    unsigned long Q;
    cin >> Q;
    constexpr unsigned long M{205891132094649UL};
    const auto& calc = [](unsigned long a, unsigned long b, unsigned long c, unsigned long d) -> unsigned long {
        auto ub{b}, lb{b}, p{M};
        while(p /= 3)if(a / p % 3 == 1 || a / p * p + p * (1 + (a / p % 3 == 2)) <= c){
            if(ub / p % 3 == 1)ub = ub / (3 * p) * 3 * p + 2 * p;
            if(lb / p % 3 == 1)lb = lb / (3 * p) * 3 * p + p - 1;
        }
        return c - a + min(ub - b + max(ub, d) - min(ub, d), b + d - 2 * lb);
    };
    for(unsigned long _{0}, a, b, c, d; _ < Q; ++_){
        cin >> a >> b >> c >> d;
        if(--a > --c){
            swap(a, c);
            swap(b, d);
        }
        if(--b > --d){
            b = M - b - 1;
            d = M - d - 1;
        }
        cout << max(calc(a, b, c, d), calc(b, a, d, c)) << endl;
    }
    return 0;
}