프랙탈 거리

민혁이가 심시티 게임에서 플레이하고 있는 도시는 교통 정체가 매우 심하다. 정체가 게임을 할 수 없을 정도로 심해지자, 민혁이는 크게 짜증이 나서 새 도시를 처음부터 다시 시작하기로 했다.

이전 도시에서 정체의 가장 큰 원인은 교차로였다. 교차로를 아무리 잘 설계해도 게임 AI 특성상 정체는 피할 수 없다. 정체를 없애려면 교차로가 아예 없는 도로를 만들면 된다. 그렇다면 교차로 없이 도시의 모든 곳을 지나가려면 어떻게 해야 할까? 민혁이는 인터넷을 뒤지다가 힐베르트 곡선(Hilbert curve)을 찾았고, 이를 도로 모양으로 쓰면 교차로 없는 도시를 만들 수 있다는 것을 알았다.

힐베르트 곡선은 다음과 같이 정의한다.

• 1번째 힐베르트 곡선은 정사각형 영역을 한 번 지나가는 컵 모양(ㄷ자) 곡선 하나이다.
• $n$번째($n \ge 2$) 힐베르트 곡선은 정사각형 영역을 네 개의 작은 정사각형으로 나눈 뒤, 각 정사각형을 $(n-1)$번째 힐베르트 곡선으로 채우고(필요에 따라 회전·반사한다), 네 조각을 직선으로 이어 하나의 연속된 곡선으로 만든 것이다.

곡선이 지나는 모든 모퉁이에는 집이 한 채씩 있으며, 곡선을 따라가는 순서대로 번호가 매겨져 있다. 가장 처음(가장 왼쪽 위)에 있는 집이 1번이고, 곡선을 따라 인접한 두 집 사이의 거리는 10이다.

몇 번째 힐베르트 곡선인지와 두 집의 번호가 주어졌을 때, 두 집 사이의 거리를 구하여라. 모든 주민은 헬리콥터를 가지고 있어 도로를 이용하지 않고 하늘을 직선으로 날아 이동한다. 따라서 이동 거리는 두 집을 잇는 직선(유클리드) 거리이다. 이착륙에 드는 거리는 무시한다.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. 각 테스트 케이스는 한 줄에 세 정수 $n$, $h$, $o$로 이루어진다. $n$은 도로가 $n$번째 힐베르트 곡선임을 나타내고, $h$와 $o$는 거리를 구할 두 집의 번호이다. ($1 \le n < 16$, $1 \le h, o < 2^{31}$)

각 테스트 케이스마다 두 집 사이의 거리를 가장 가까운 정수로 반올림하여 한 줄에 하나씩 출력한다.