G. Fractal Streets

With a growing desire for modernization in our increasingly larger cities comes a need for new street designs. Chris is one of the unfortunate city planners responsible for these designs. Each year the demands keep increasing, and this year he has even been asked to design a completely new city.

More work is not something Chris needs right now, since like any good bureaucrat, he is extremely lazy. Given that this is a character trait he has in common with most computer scientists it should come as no surprise that one of his closest friends, Paul, is in fact a computer scientist. And it was Paul who suggested the brilliant idea that has made Chris a hero among his peers: Fractal Streets! By using a Hilbert curve, he can easily fill in rectangular plots of arbitrary size with very little work.

A Hilbert curve of order 1 consists of one “cup”. In a Hilbert curve of order 2 that cup is replaced by four smaller but identical cups and three connecting roads. In a Hilbert curve of order 3 those four cups are in turn replaced by four identical but still smaller cups and three connecting roads, etc. At each corner of a cup a driveway (with mailbox) is placed for a house, with a simple successive numbering. The house in the top left corner has number 1, and the distance between two adjacent houses is 10 m.

The situation is shown graphically in figure 2. As you can see the Fractal Streets concept successfully eliminates the need for boring street grids, while still requiring very little effort from our bureaucrats.

(a) Order 1                                                  (b) Order 2                                               (c) Order 3

Figure 2: Hilbert curves of order 1, 2 and 3, with the location of the houses indicated.

As a token of their gratitude, several mayors have offered Chris a house in one of the many new neighborhoods built with his own new scheme. Chris would now like to know which of these offerings will get him a house closest to the local city planning office (of course each of these new neighborhoods has one). Luckily he will not have to actually drive along the street, because his new company “car” is one of those new flying cars. This high-tech vehicle allows him to travel in a straight line from his driveway to the driveway of his new office. Can you write a program to determine the distance he will have to fly for each offer (excluding the vertical distance at takeoff and landing)?

typedef struct{
	int x;
	int y;
}point;


point solve(long order,long num){
	if(order == 1){
		point a;
		if(num == 1){
			a.x = 1;
			a.y = 1;
		}
		else if(num == 2){
			a.x = 2;
			a.y = 1;
		}
		else if(num == 3){
			a.x = 2;
			a.y = 2;
		}
		else if(num == 4){
			a.x = 1;
			a.y = 2;
		}
		return a;
	}
	long div = pow(2.0,2*(order-1));
	FOR(i, 4){
		if(num <= (i+1)*div){
			
			if(i==0){
				point tmp = solve(order-1, div - (num-i*div-1));
				
				long double dx = (pow(2.0,order-1)+1)/2.0;
				long double dy = dx;

				long double cx = tmp.x - dx;
				long double cy = dy - tmp.y;
				
				long double fx = cy;
				long double fy = -cx;
				
				tmp.x = dx + fx;
				tmp.y = dy - fy;
		
				
				return tmp;
			}
			else if(i==1){
				point tmp = solve(order-1, num-i*div);
				tmp.x = tmp.x + pow(2.0,order-1);
				return tmp;
			}
			else if(i==2){
				point tmp = solve(order-1, num-i*div);
				tmp.x = tmp.x + pow(2.0,order-1);
				tmp.y = tmp.y + pow(2.0,order-1);
				return tmp;
			}
			if(i==3){
				
				point tmp = solve(order-1, div - (num-i*div-1));
				long double dx = (pow(2.0,order-1)+1)/2.0;
				long double dy = dx;

				long double cx = tmp.x - dx;
				long double cy = dy - tmp.y;
				
				long double fx = -cy;
				long double fy = cx;
				
				tmp.x = dx + fx;
				tmp.y = dy - fy;

				
				tmp.y = tmp.y + pow(2.0,order-1);
				return tmp;
			}
		}
	}
}

int main(){
	int testCase;
	cin >> testCase;
	FOR(testi, testCase){
		long o,a,b;
		cin >> o >> a >> b;
		point pa = solve(o,a);
		point pb = solve(o,b);
		long double tmp = (pa.x-pb.x)*(pa.x-pb.x)+(pa.y-pb.y)*(pa.y-pb.y);
		long result = (long)(sqrt(tmp)*10+0.5);
		cout << result << endl;
	}
	
	return 0;
}