program fractal_shortest_path
  implicit none
  integer, parameter :: n = 30
  integer :: q, i, k
  integer(8) :: a, b, c, d, pow(0:n) = 0, p, x, y, z, w, m, s, t
  logical :: fx, fy
  pow(0) = 1
  do i = 1, n
    pow(i) = pow(i - 1) * 3
  end do
  read(*,*) q
  do i = 1, q
    read(*,*) a, b, c, d
    a = a - 1
    b = b - 1
    c = c - 1
    d = d - 1
    do k = n, 0, -1
      p = pow(k)
      x = a / p
      y = b / p
      z = c / p
      w = d / p
      fx = x == z .and. mod(x, 3) == 1 .and. abs(y - w) >= 2
      fy = y == w .and. mod(y, 3) == 1 .and. abs(x - z) >= 2
      if (fx .or. fy) then
        if (fx) then
          s = mod(a, p)
          t = mod(c, p)
          m = abs(c - a)
        else
          s = mod(b, p)
          t = mod(d, p)
          m = abs(d - b)
        end if
        m = m + min(s + t + 2, p * 2 - s - t)
        goto 100
      end if
    end do
    m = abs(c - a) + abs(d - b)
    100 write(*,'(i0)') m
  end do
end program fractal_shortest_path