#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <string>
using namespace std;
#define ll signed long long 

int main() {
  int Q;
  cin >> Q;
  for (int q = 0; q < Q; ++q) {
    ll x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;
    --x1; --y1; --x2; --y2;

    ll ans = -1;
    for (ll i = pow(3ll, 30ll); i > 1; i /= 3) {
      if (x1 / i == x2 / i &&
          i / 3 <= x1 % i && x1 % i < i / 3 * 2 &&
          i / 3 <= x2 % i && x2 % i < i / 3 * 2) {
        if (y1 / (i / 3) < y2 / (i / 3) - 1 ||
            y2 / (i / 3) < y1 / (i / 3) - 1) {
          ans = abs(y2 - y1);
          ans += min((x1 % i) - (i / 3 - 1) + (x2 % i) - (i / 3 - 1),
                     i / 3 * 2 - (x1 % i) + i / 3 * 2 - (x2 % i));
          break;
        }
      }

      
      if (y1 / i == y2 / i &&
          i / 3 <= y1 % i && y1 % i < i / 3 * 2 &&
          i / 3 <= y2 % i && y2 % i < i / 3 * 2) {
        if (x1 / (i / 3) < x2 / (i / 3) - 1 ||
            x2 / (i / 3) < x1 / (i / 3) - 1) {
          ans = abs(x2 - x1);
          ans += min((y1 % i) - (i / 3 - 1) + (y2 % i) - (i / 3 - 1),
                     i / 3 * 2 - (y1 % i) + i / 3 * 2 - (y2 % i));
          break;
        }
      }
      if (ans >= 0) {
        break;
      }
    }
    if (ans >= 0) {
      cout << ans << endl;
    } else {
      cout << abs(x2 - x1) + (abs(y2 - y1)) << endl;
    }
  }
  return 0;
}


/*
...........................
.*..*..*..*..*..*..*..*..*.
...........................
...***......***......***...
.*.***.*..*.***.*..*.***.*.
...***......***......***...
...........................
.*..*..*..*..*..*..*..*..*.
...........................
.........*********.........
.*..*..*.*********.*..*..*.
.........*********.........
...***...*********...***...
.*.***.*.*********.*.***.*.
...***...*********...***...
.........*********.........
.*..*..*.*********.*..*..*.
.........*********.........
...........................
.*..*..*..*..*..*..*..*..*.
...........................
...***......***......***...
.*.***.*..*.***.*..*.***.*.
...***......***......***...
...........................
.*..*..*..*..*..*..*..*..*.
...........................
*/
