프랙탈 거리

민혁이가 심시티 게임에서 플레이하고 있는 도시는 교통 정체가 상당히 심하다. 교통 정체는 게임을 플레이 할 수 없을 정도로 심해졌고, 민혁이는 엄청난 짜증을 느꼈다. 따라서, 민혁이는 새 도시를 시작하기로 결심했다.

이전 도시에서 교통 정체의 가장 큰 원인은 교차로였다. 교차로를 아무리 잘 설계해도, 게임 상의 AI 문제로 교통 정체는 피할 수 없는 선택이다. 교통 정체를 피하기 위해서는 교차로가 없는 도로를 만들면 된다. 

어떻게 교차로 없이 도시의 모든 곳을 방문할 수 있을까? 민혁이는 인터넷에서 열심히 살펴보다가 힐베르트 곡선을 찾았다. 힐베르트 곡선을 이용하면, 교차로 없이 도시를 만들 수 있을 것이다.

첫 번째 힐베르트 곡선은 컵(왼쪽 그림에 나와있는 ㄷ자) 하나로 이루어져 있다. 두 번째 힐베르트 곡선은 구역을 네 개의 정사각형으로 나누고, 각각의 정사각형에 컵을 채운 다음에 네 컵을 직선으로 연결한 것이다.

힐베르트 곡선에 대한 설명은 4645번에 잘 나와 있기 때문에, 이 문제를 참고하면 된다.

모든 모퉁이에는 집이 하나씩 있고, 순서대로 번호가 매겨져 있다. 가장 왼쪽 위에 있는 집이 1번이고, 인접한 두 집 사이의 거리는 10이다.

몇 번째 힐베르트 곡선인지와 두 집의 번호가 주어졌을 때, 두 집 사이의 거리를 구하는 프로그램을 작성하시오. 모든 주민은 헬리콥터를 가지고 있어서, 도로를 이용하지 않고 하늘을 날아서 이동한다. 헬리콥터의 이륙과 착륙하는데 필요한 거리는 무시하며, 항상 최단거리를 이용한다.

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 세 정수 n, h, o 가 주어진다. n은 마을의 도로가 n번째 힐베르트 곡선임을 나타내며, h와 o는 거리를 구해야 하는 두 집의 번호이다. (n < 16, h,o < 231)

각 테스트 케이스에 대해서, 입력으로 주어진 두 집의 거리를 가까운 정수로 반올림해서 출력한다.