Untitled

#include <iostream>
#include <vector>
#include <queue>
#include <set>


using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<ll, pll> plll;

const bool DEBUG = true;


const ll T_ZONE = 0, I_ZONE = 1, NO_ZONE = 2, NE_ZONE = 3, SE_ZONE = 4, SO_ZONE = 5, OUT_ZONE = 6;

void rotate_clockwise(ll& x, ll& y){
    ll aux = x;
    x = y;
    y = -aux;
}

void rotate_counterclockwise(ll& x, ll& y){
    ll aux = x;
    x = -y;
    y = aux;
}


ll getZone(ll siz, ll x, ll y){
    if (abs(x) >= siz || abs(y) >= siz) return OUT_ZONE;
    if (x == 0 && y > 0) return I_ZONE;
    if (y == 0) return T_ZONE;
    if (x == 0) return T_ZONE;
    if (x < 0 && y < 0) return SO_ZONE;
    if (x < 0 && y > 0) return NO_ZONE;
    if (x > 0 && y > 0) return NE_ZONE;
    return SE_ZONE;
}

ll getZone(ll siz, pll a){
    return getZone(siz, a.first,a.second);
}

ll manhattan(ll x, ll y, ll xx, ll yy){
    return abs(xx - x) + abs(yy-y);
}

ll getExteriorDist(ll siz, ll x, ll y, ll xx, ll yy){
    if (abs(x) < siz && abs(xx) < siz){
        if ((y >= siz && yy <= -siz) || (y <= -siz && yy >= siz)){
            return abs(yy - y) + min(siz - x + siz - xx, siz + x + siz + xx);
        }
    }
    if (abs(y) < siz && abs(yy) < siz){
        if ((x >= siz && xx <= -siz) || (x <= -siz && xx >= siz)){
            return abs(xx - x) + min(siz - y + siz - yy, siz + y + siz + yy);
        }
    }
    return manhattan(x,y,xx,yy);
}

ll getTDist(ll siz, ll x, ll y){
    return abs(x) + abs(siz + y);
}


plll getTotalExit(ll N, ll x, ll y){

    ll siz = (1LL << N)/2;
    ll z = getZone(siz,x,y);

    if (z == T_ZONE){
        return plll(getTDist(siz,x,y), pll(0, -siz));
    }
    if (z == I_ZONE){
        return plll(siz - y, pll(0, siz));
    }
    if (z == OUT_ZONE){
        return plll(0, pll(x, y));
    }

    if (z == NE_ZONE || z == NO_ZONE){
        y-= siz/2;
    }
    if (z == SE_ZONE || z == SO_ZONE){
        y+= siz/2;
    }
    if (z == NO_ZONE || z == SO_ZONE){
        x += siz/2;
    }
    if (z == NE_ZONE || z == SE_ZONE){
        x -= siz/2;
    }
    if (z == SO_ZONE){
        rotate_counterclockwise(x,y);
    }
    if (z == SE_ZONE){
        rotate_clockwise(x,y);
    }

    plll e = getTotalExit(N-1, x, y);


    pll ePos = e.second;
    if (z == SO_ZONE){
        rotate_clockwise(e.second.first, e.second.second);
    }
    if (z == SE_ZONE){
        rotate_counterclockwise(e.second.first, e.second.second);
    }
    if (z == NE_ZONE || z == NO_ZONE){
        e.second.second+= siz/2;
    }
    if (z == SE_ZONE || z == SO_ZONE){
        e.second.second-= siz/2;
    }
    if (z == NO_ZONE || z == SO_ZONE){
        e.second.first -= siz/2;
    }
    if (z == NE_ZONE || z == SE_ZONE){
       e.second.first += siz/2;
    }

    ll newZ = getZone(siz, e.second);
    if (newZ == OUT_ZONE) return e;
    if (newZ == T_ZONE){
        return plll(e.first + getTDist(siz,e.second.first,e.second.second), pll(0, -siz));
    }
    if (newZ == I_ZONE){
        return plll(e.first + siz - e.second.second, pll(0, siz));
    }
    if (DEBUG) cerr << "GIGA FAIL" << endl;
    return plll(-1, pll(0,0));
}

plll getExit(ll N, ll x, ll y){
    ll siz = (1LL << N)/2;
    ll z = getZone(siz,x,y);

    
    if (DEBUG) cerr << "CHECKING TOTAL EXIT " << N << "         " << x << " " << y << "      " << z << endl;

    if (z == T_ZONE || z == I_ZONE || z == OUT_ZONE){
        return plll(0, pll(x,y));
    }

    if (z == NE_ZONE || z == NO_ZONE){
        y-= siz/2;
    }
    if (z == SE_ZONE || z == SO_ZONE){
        y+= siz/2;
    }
    if (z == NO_ZONE || z == SO_ZONE){
        x += siz/2;
    }
    if (z == NE_ZONE || z == SE_ZONE){
        x -= siz/2;
    }
    if (z == SO_ZONE){
        rotate_counterclockwise(x,y);
    }
    if (z == SE_ZONE){
        rotate_clockwise(x,y);
    }

    plll e = getTotalExit(N-1, x, y);

    if (DEBUG) cerr << "GOT ANSWER " << e.first << " " << e.second.first << " " << e.second.second << endl;
    pll ePos = e.second;
    if (z == SO_ZONE){
        rotate_clockwise(e.second.first, e.second.second);
    }
    if (z == SE_ZONE){
        rotate_counterclockwise(e.second.first, e.second.second);
    }
    if (z == NE_ZONE || z == NO_ZONE){
        e.second.second+= siz/2;
    }
    if (z == SE_ZONE || z == SO_ZONE){
        e.second.second-= siz/2;
    }
    if (z == NO_ZONE || z == SO_ZONE){
        e.second.first -= siz/2;
    }
    if (z == NE_ZONE || z == SE_ZONE){
       e.second.first += siz/2;
    }

    if (DEBUG) cerr << "GOT ANSWER TRANSFORMED " << e.first << " " << e.second.first << " " << e.second.second << endl;

    ll newZ = getZone(siz, e.second);
    if (newZ == T_ZONE || newZ == I_ZONE || newZ == OUT_ZONE) return e;
    if (DEBUG) cerr << "GIGA FAIL 2" << endl;
    return plll(-1, pll(0,0));
}

ll findShortestPath(ll N, ll x,ll y, ll xx,ll yy){
    ll siz = (1LL << N)/2;
    ll z1 = getZone(siz, x,y);
    ll z2 = getZone(siz, xx,yy);


    if (DEBUG) cerr << "ANALYZING SHORTEST PATH " << siz <<  "    " <<  x << " " << y << "    " << xx << " " << yy << endl;

    if (DEBUG) cerr << "ZONE 1 " << z1 << endl;
    if (DEBUG) cerr << "ZONE 2 " << z2 << endl;

    if (z1 > z2){
        swap(z1, z2);
        swap(x,xx);
        swap(y,yy);
    }

    //CASE WHERE BOTH POINTS ARE NOT ON QUADRANTS
    if (z1 == T_ZONE && z2 == T_ZONE){
        return manhattan(x,y,xx,yy);
    }
    if (z1 == T_ZONE && z2 == I_ZONE){
        return getTDist(siz, x,y) + (siz-yy) + getExteriorDist(siz, 0, -siz, 0, siz);
    }
    if (z1 == T_ZONE && z2 == OUT_ZONE){
        return getTDist(siz, x,y) + getExteriorDist(siz, 0, -siz, xx, yy);
    }
    if (z1 == I_ZONE && z2 == I_ZONE){
        return manhattan(x,y,xx,yy);
    }
    if (z1 == I_ZONE && z2 == OUT_ZONE){
        (siz-y) + getExteriorDist(siz, 0, siz, xx,yy);
    }
    if (z1 == OUT_ZONE && z2 == OUT_ZONE){
        return getExteriorDist(siz, x,y, xx,yy);
    }

    if (N == 1) return 0;

    //ONE POINT ON QUADRANT, THE OTHER NOT
    if (z1 == T_ZONE){
        plll e2 = getExit(N, xx,yy);
        if (getZone(siz, e2.second) == T_ZONE){
            return e2.first + manhattan(e2.second.first, e2.second.second, x, y);
        }
        if (getZone(siz, e2.second) == I_ZONE){
            return e2.first + getTDist(siz, x,y) + (siz - e2.second.second) + getExteriorDist(siz, 0, -siz, 0, siz);
        }
        return e2.first + getTDist(siz, x,y) + getExteriorDist(siz, 0, -siz, e2.second.first, e2.second.second);
    }
    if (z1 == I_ZONE){
        plll e2 = getExit(N, xx,yy);
        if (getZone(siz, e2.second) == T_ZONE){
            return e2.first + getTDist(siz, e2.second.first, e2.second.second) + (siz - y) + getExteriorDist(siz, 0, -siz, 0, siz);
        }
        if (getZone(siz, e2.second) == I_ZONE){
            return e2.first + manhattan(e2.second.first, e2.second.second, x, y);
        }
        return e2.first + (siz - y) + getExteriorDist(siz, 0, siz, e2.second.first, e2.second.second);
    }
    if (z2 == OUT_ZONE){
        plll e1 = getExit(N, x,y);
        if (getZone(siz, e1.second) == T_ZONE){
            return e1.first + getTDist(siz, e1.second.first, e1.second.second) + getExteriorDist(siz, 0, -siz, xx, yy);
        }
        if (getZone(siz, e1.second) == I_ZONE){
            return e1.first + (siz - e1.second.second) + getExteriorDist(siz, 0, siz, xx, yy);
        }
        return e1.first + getExteriorDist(siz, e1.second.first, e1.second.second, xx, yy);
    }

    //BOTH POINTS ON QUADRANTS

    plll e1 = getExit(N, x,y);
    plll e2 = getExit(N, xx,yy);
    ll ze1 = getZone(siz, e1.second); //these can only be T, I or OUT
    ll ze2 = getZone(siz, e2.second); //these can only be T, I or OUT
    if (ze2 < ze1){
        swap(ze2, ze1);
        swap(e2, e1);
        swap(x,xx);
        swap(y,yy);
        swap(z1, z2);
    }

    if (DEBUG) cerr << "EXIT 1 " << e1.first << " " << e1.second.first << " " << e1.second.second << endl;
    if (DEBUG) cerr << "EXIT 2 " << e2.first << " " << e2.second.first << " " << e2.second.second << endl;

    //DIFF QUADS OR DIFF EXIT
    if (z1 != z2 || e1.second != e2.second){
        if (ze1 == T_ZONE){
            if (ze2 == T_ZONE){
                return e1.first + e2.first + manhattan(e1.second.first, e1.second.second, e2.second.first, e2.second.second);
            }
            if (ze2 == I_ZONE){
                return e1.first + e2.first + getTDist(siz, e1.second.first, e1.second.second) + (siz - e2.second.second) + getExteriorDist(siz, 0, -siz, 0, siz);
            }
            if (ze2 == OUT_ZONE){
                return e1.first + e2.first + getTDist(siz, e1.second.first, e1.second.second) + getExteriorDist(siz, 0, -siz, e2.second.first, e2.second.second);
            }
        }

        if (ze1 == I_ZONE){
            if (ze2 == I_ZONE){
                return e1.first + e2.first + manhattan(e1.second.first, e1.second.second, e2.second.first, e2.second.second);
            }
            if (ze2 == OUT_ZONE){
                return e1.first + e2.first + (siz - e1.second.second) + getExteriorDist(siz, 0, siz, e2.second.first, e2.second.second);
            }
        }
        if (ze1 == OUT_ZONE){
            return e1.first + e2.first + getExteriorDist(siz, e1.second.first, e1.second.second, e2.second.first, e2.second.second);
        }
    }
    //SAME QUADS SAME EXIT
    if (z1 == NE_ZONE || z1 == NO_ZONE){
        y-= siz/2;
        yy-= siz/2;
    }
    if (z1 == SE_ZONE || z1 == SO_ZONE){
        y+= siz/2;
        yy+= siz/2;
    }
    if (z1 == NO_ZONE || z1 == SO_ZONE){
        x += siz/2;
        xx += siz/2;
    }
    if (z1 == NE_ZONE || z1 == SE_ZONE){
        x -= siz/2;
        xx -= siz/2;
    }
    if (z1 == SO_ZONE){
        rotate_counterclockwise(x,y);
        rotate_counterclockwise(xx,yy);
    }
    if (z1 == SE_ZONE){
        rotate_clockwise(x,y);
        rotate_clockwise(xx,yy);
    }
    return findShortestPath(N-1, x, y, xx, yy);
}

const int TEST_N = 4;

void generateWalls(){

}

typedef vector<ll> VLL;
typedef vector<VLL> VVLL;
typedef pair<pll, pll> ppll;
typedef set<ppll> sppll;

sppll unconnected;

const vector<pll> dirs{pll(1, 0), pll(0,1), pll(-1, 0), pll(0, -1)};
const int EAST = 0;
const int NORTH = 1;
const int WEST = 2;
const int SOUTH = 3;

VVLL dists;

bool canAccess(pll a, pll b){
    if (b.first < -1 || b.first >= (1 << TEST_N)) return false;
    if (b.second < -1 || b.second >= (1 << TEST_N)) return false;
    return unconnected.find(ppll(a, b)) == unconnected.end();
}

ll getShortestDist(ll x, ll y, ll xx, ll yy){
    int length = (1 << TEST_N) + 1;
    dists = VVLL(length, VLL(length, 100000));
    queue<pll> q;
    q.push(pll(x,y));
    dists[x+1][y+1] = 0;
    while (!q.empty()){
        pll f = q.front();
        q.pop();
        int df = dists[f.first+1][f.second+1];
        if (f.first == xx && f.second == yy) return df;
        for (int i = 0; i < 4; ++i){
            pll x = f;
            x.first += dirs[i].first;
            x.second += dirs[i].second; 
            if (canAccess(f,x)){
                int oldDist = dists[x.first+1][x.second+1];
                if (oldDist > df + 1){
                    dists[x.first+1][x.second+1] = df+1;
                    q.push(x);
                }
            }
        }
    }
    return -1;
}

struct vect{
    pll pos;
    int dir;

    void advance(){
        ll x = pos.first;
        ll y = pos.second;
        if (dir == NORTH){
            //cerr << "inserting " << x-1 << " " << y << "         " << pos.first << " " << pos.second << endl;
            unconnected.insert(ppll(pos, pll(x-1, y)));
            unconnected.insert(ppll(pll(x-1, y), pos));
        }
        else if (dir == SOUTH){
            //cerr << "inserting " << x-1 << " " << y-1 << "         " << x << " " << y-1 << endl;
            unconnected.insert(ppll(pll(x-1, y-1), pll(x, y-1)));
            unconnected.insert(ppll(pll(x, y-1), pll(x-1, y-1)));
        }
        else if (dir == EAST){
            //cerr << "inserting " << x << " " << y << "         " << x << " " << y-1 << endl;
            unconnected.insert(ppll(pos, pll(x, y-1)));
            unconnected.insert(ppll(pll(x, y-1), pos));     
        }
        else {
            //cerr << "inserting " << x-1 << " " << y << "         " << x-1 << " " << y-1 << endl;
            unconnected.insert(ppll(pll(x-1, y), pll(x-1, y-1)));
            unconnected.insert(ppll(pll(x-1, y-1), pll(x-1, y)));
        }
        pos.first += dirs[dir].first;
        pos.second += dirs[dir].second;
    }

    void rotateRight(){
        dir = (dir + 3)%4;
    }

    void rotateLeft(){
        dir = (dir + 1)%4;
    }
};

vect v;

void generateUnconnectedA (int n);

void generateUnconnectedB(int n){
    if (n == 0) return;
    v.rotateRight();
    generateUnconnectedA(n-1);
    v.advance();
    v.rotateLeft();
    generateUnconnectedB(n-1);
    v.advance();
    generateUnconnectedB(n-1);
    v.rotateLeft();
    v.advance();
    generateUnconnectedA(n-1);
    v.rotateRight();
}

void generateUnconnectedA(int n){
    if (n == 0) return;
    v.rotateLeft();
    generateUnconnectedB(n-1);
    v.advance();
    v.rotateRight();
    generateUnconnectedA(n-1);
    v.advance();
    generateUnconnectedA(n-1);
    v.rotateRight();
    v.advance();
    generateUnconnectedB(n-1);
    v.rotateLeft();
}

void gUnc(){
    v.pos = pll(0,0);
    v.dir = 0;
    generateUnconnectedA(TEST_N);
}

int main(){
    ll k;
    cin >> k;
    for (ll i = 0; i < k; ++i){
        ll n, x, y, xx, yy;
        cin >> n >> x >> y >> xx >> yy;
        ll siz = ((1LL << n)/2) - 1;
        x-= siz;
        y-= siz;
        xx -= siz;
        yy -= siz;
        cout << findShortestPath(n, x, y, xx, yy) << endl;
    }
    /*gUnc();
    ll siz = ((1LL << TEST_N)/2) - 1;
    for (int i = -1; i < (1 << TEST_N) ; ++i){
        for (int j = -1; j < (1 << TEST_N); ++j){
            for (int ii = -1; ii < (1 << TEST_N); ++ii){
                for (int jj = -1; jj < (1 << TEST_N) ; ++jj){
                    ll goodDist = getShortestDist(i,j,ii,jj);
                    ll badDist = findShortestPath(TEST_N, i-siz, j-siz, ii-siz, jj-siz);
                    if (goodDist != badDist){
                        cout << "DIFF " << i << " " << j << " " << ii << " " << jj << ":   " << goodDist << " vs " << badDist << endl; 
                    }
                }
            }
        }
    }*/
}