/*
 * Here-There / IPSC 2007, solver
 * (c) Goober
 */

#include <stdio.h>

typedef long long NUMBER;

NUMBER min(NUMBER x, NUMBER y) { return (x < y) ? x : y; }
NUMBER mabs(NUMBER x) { return (x >= 0) ? x : -x; }

NUMBER delta(NUMBER depth, NUMBER x1, NUMBER y1, NUMBER x2, NUMBER y2)
{
  NUMBER sizer;

  sizer = 1;
  while(--depth) sizer *= 3;

// Adjust x1 and x2 for the "is there a hole in between" check
  x1 = (x1 + (3*sizer+1)/2) / 3;
  x2 = (x2 + (3*sizer+1)/2) / 3;
  while(sizer > 0)
  {
// Different stripes -> no detour
    if ((y1/sizer) != (y2/sizer))
	return 0;
// Middle stripe with a hole in between? Detour!
    if ((y1/sizer) == 1 && (x1 / sizer != x2 / sizer))
        return 2*min(min(y1-sizer, 2*sizer - 1 - y1),
                     min(y2-sizer, 2*sizer - 1 - y2)) + 2;
    y1 %= sizer; y2 %= sizer;
    sizer /= 3;
  }
  return 0;
}

int main()
{
  NUMBER x1, y1, x2, y2, d;
  int t;
   
  scanf("%d", &t);
  while(t--)
  {
    scanf("%llu %llu %llu %llu %llu", &d, &x1, &y1, &x2, &y2);
    x1--; y1--; x2--; y2--;
    printf("%llu\n", mabs(x2-x1) + mabs(y2-y1) + 
                     delta(d, x1, y1, x2, y2) +
                     delta(d, y1, x1, y2, x2));
  }
  return 0;
}