#include <stdio.h>

#include <stdlib.h>

#include <time.h>

#include <string.h>

#include <algorithm>

#include <iostream>

#include <map>

#include <queue>

#include <set>

#include <string>

#include <vector>

#include <bits/stdc++.h>

using namespace std;



const double TL = 1.5 * CLOCKS_PER_SEC;

mt19937 rng((unsigned int) chrono::steady_clock::now().time_since_epoch().count());

#define clr(x, y) memset(x, y, sizeof(x))

#define forn(i, n) for (int i = 0; i < n; i++)

#define LL long long



int n;

LL s[50];



vector<LL> cal(LL x, LL y, int d) {

  LL sx = (x - 1) / s[d] + 1;

  LL tx = (x - 1) % s[d] + 1;

  LL sy = (y - 1) / s[d] + 1;

  LL ty = (y - 1) % s[d] + 1;



  if(tx > s[d - 1] && tx <= s[d - 1] * 2) {

    int p = ty <= s[d - 1] ? 0 : 1;

    return {1, sx, sy + p, tx - s[d - 1], s[d - 1] * 2 - tx + 1};

  }

  if(ty > s[d - 1] && ty <= s[d - 1] * 2) {

    int p = tx <= s[d - 1] ? 0 : 1;

    return {2, sy, sx + p, ty - s[d - 1], s[d - 1] * 2 - ty + 1};

  }

  return {0, 0, 0, 0};

}



int main() {

  //auto start_clock = clock();

 // freopen("in", "r", stdin);

  s[0] = 1;

  for(int i = 1; i <= 30; i++) {

    s[i] = s[i - 1] * 3;

  }

  scanf("%d", &n);

  while(n--) {

    LL x1, y1, x2, y2;

    cin >> x1 >> y1 >> x2 >> y2;

    LL ans = 0;

    for(int i = 30; i >= 0; i--) {

      if(i == 0) {

        ans = abs(x1 - x2) + abs(y1 - y2);

      }

      else {

        auto v1 = cal(x1, y1, i);

        auto v2 = cal(x2, y2, i);

        if(v1[0] == v2[0] && v1[0] != 0 && v1[1] == v2[1] && v1[2] != v2[2]) {

          LL t = min(v1[3] + v2[3], v1[4] + v2[4]);

          if(abs(v1[0]) == 1) {

            t += abs(y1 - y2);

          }

          else {

            t += abs(x1 - x2);

          }

          ans = t;

          break;

        }

      }

    }

    cout << ans << endl;

  }



  return 0;

}

