program fractal_shortest_path
  implicit none
  integer :: q, i
  integer(8) :: a, b, c, d
  read(*,*) q
  do i = 1, q
    read(*,*) a, b, c, d
    write(*,'(i0)') distance(a, b, c, d)
  end do
contains
  integer(8) function distance(a, b, c, d) result(res)
    integer(8), intent(in) :: a, b, c, d
    res = abs(c - a) + abs(d - b) + min(extra(a - 1, b - 1, c - 1, d - 1), &
      extra(b - 1, a - 1, d - 1, c - 1)) * 2
  end
  integer(8) function extra(x1, y1, x2, y2) result(res)
    integer(8), intent(in) :: x1, y1, x2, y2
    integer(8) :: t, tmp
    integer :: i
    res = 0
    t = 1
    do i = 1, 36
      if (x1 / t == x2 / t .and. between(x1 / t, y1 / t, y2 / t)) then
        tmp = min(min(mod(x1, t), mod(x2, t)) + 1, &
          t - max(mod(x1, t), mod(x2, t)))
        res = max(res, tmp)
      end if
      t = t * 3
    end do
  end
  logical function between(x, y1, y2) result(res)
    integer(8), intent(in) :: x, y1, y2
    integer(8) :: a, b1, b2, b
    res = .false.
    b1 = min(y1, y2) + 1
    b2 = max(y1, y2) - 1
    if (b1 > b2) return
    do while (a > 0)
      if (mod(a, 3) == 1) then
        if (b2 - b1 > 3) then
          res = .true.
          return
        end if
        do b = b1, b2
          if (mod(b, 3) == 1) then
            res = .true.
            return
          end if
        end do
      end if
      a = a / 3
      b1 = b1 / 3
      b2 = b2 / 3
    end do
  end
end program fractal_shortest_path