// ※※※ 解答不能 ※※※
// https://img.atcoder.jp/panasonic2020/editorial.pdf
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define _abs(x) ((x) > 0 ? (x) : -(x))

// 二点間を妨害するような黒マスの連結成分があるかを計算？
// @param x:  x座標(スタート地点).
// @param y1: y座標(スタート地点).
// @param y2: y座標(ゴール地点).
// @return : 妨害する黒マスの連結成分があるかどうか.
bool between(LL x, LL y1, LL y2){
    if(y1 > y2) swap(y1, y2);
    y1++, y2--;
    if(!(y1 <= y2)) return false;
    while(x > 0){
        if(x % 3 == 1){
            if(y2 - y1 > 3) return true;
            for(LL y = y1; y <= y2; y++) if(y % 3 == 1) return true;
        }
        x /= 3;
        y1 /= 3;
        y2 /= 3;
    }
    return false;
}

// 迂回する距離？を計算.
// @param x1: x座標(スタート地点).
// @param y1: y座標(スタート地点).
// @param x2: x座標(ゴール地点).
// @param y2: y座標(ゴール地点).
// @return : スタート地点からゴール地点までの迂回する距離を返却.
LL get_extra(LL x1, LL y1, LL x2, LL y2){
    LL ans = 0, three = 1;
    int i;
    rep(i, 35){
        if(x1 / three == x2 / three && between(x1 / three, y1 / three, y2 / three)){
            LL tmp = min(min(x1 % three, x2 % three) + 1, three - max(x1 % three, x2 % three));
            ans = max(ans, tmp);
        }
        three *= 3;
    }
    return ans;
}

// 二点間の距離を求める.
// @param x1: x座標(スタート地点).
// @param y1: y座標(スタート地点).
// @param x2: x座標(ゴール地点).
// @param y2: y座標(ゴール地点).
// @return : スタート地点からゴール地点までの距離を返却.
LL get_dist(LL x1, LL y1, LL x2, LL y2){
    return _abs(x1 - x2) + _abs(y1 - y2) + 2 * max(get_extra(x1, y1, x2, y2), get_extra(y1, x1, y2, x2));
}

int main(){
    
    // 1. 入力情報.
    int Q;
    scanf("%d", &Q);
    
    // 2. クエリに回答.
    rep(i, Q){
        LL a, b, c, d;
        scanf("%lld %lld %lld %lld", &a, &b, &c, &d);
        a--, b--, c--, d--;
        printf("%lld\n", get_dist(a, b, c, d));
    }
    return 0;
    
}