Fractal Distance

The city Minhyuk is playing in SimCity suffers from terrible traffic jams. The jams got so bad that the game became unplayable, and Minhyuk grew so frustrated that he decided to start a brand-new city from scratch.

In his previous city, the biggest cause of jams was intersections. No matter how well you design an intersection, the game's AI makes jams unavoidable. To get rid of them, you just have to build roads with no intersections at all. But how can you pass through every part of a city without a single intersection? Searching online, Minhyuk found the Hilbert curve, and realized that using it as the shape of the roads lets him build a city with no intersections.

The Hilbert curve is defined as follows.

• The 1st Hilbert curve is a single cup-shaped curve (a bracket, like ┐└) that passes through a square region once.
• The $n$-th Hilbert curve ($n \ge 2$) splits the square region into four smaller squares, fills each smaller square with an $(n-1)$-th Hilbert curve (rotating/reflecting it as needed), and joins the four pieces with straight segments into one continuous curve.

At every corner the curve passes through there is exactly one house, and the houses are numbered in the order the curve visits them. The very first house (top-left) is number 1, and the distance between two houses adjacent along the curve is 10.

Given which Hilbert curve is used and the numbers of two houses, compute the distance between them. Every resident owns a helicopter and flies through the air in a straight line instead of using the roads, so the travel distance is the straight-line (Euclidean) distance between the two houses. The distance needed to take off and land is ignored.

The first line contains the number of test cases $T$. Each test case is a single line with three integers $n$, $h$, and $o$. Here $n$ means the roads form the $n$-th Hilbert curve, and $h$ and $o$ are the numbers of the two houses whose distance you must find. ($1 \le n < 16$, $1 \le h, o < 2^{31}$)

For each test case, print the distance between the two given houses rounded to the nearest integer, one per line.