케플러

두 번째 자이로스코프가 고장난 뒤, 천문 망원경 "케플러"는 더 이상 사용할 수 없게 되었다. NASA는 이 손실을 메우기 위해 다른 망원경을 우주로 발사하기로 했다. 망원경에 전력을 공급하기 위해 태양 전지를 사용하기로 했다. 태양 전지의 원판은 1×1 크기의 칸으로 이루어진 n×m 크기의 직사각형 패널이다.

아쉽게도 전지를 펼친 상태로 궤도에 운반할 수는 없다. 운반을 쉽게 하기 위해 패널은 얇은 재료로 만들어져 어떤 칸 경계를 따라서도 접을 수 있다. 과학자들은 전지가 1×1 크기로 접힌 채 우주로 날아가기로 했다.

이를 위해 그들은 전지 원판을 다음과 같이 다룬다. 현재 원판의 한 변의 길이가 짝수이면 그 변을 따라 원판을 반으로 접을 수 있고, 그러면 크기가 절반인 패널이 된다(패널의 두께는 무시한다). 만약 어떤 변의 길이가 홀수라면(패널의 크기가 (2n+1)×m이라면), 정밀 레이저로 m의 시간 동안 1×m 크기의 조각을 잘라낸 다음, 길이 2n인 변을 따라 반으로 접을 수 있다. 잘라낸 패널 조각은 버린다. 결과적으로 과학자들은 1×1 크기의 패널을 얻고, 이 패널은 궤도로 날아가 그곳에서 펼쳐진다.

레이저는 모든 접기보다 훨씬 오래 작동한다. 주어진 방식으로 처음 원판을 1×1 크기의 정사각형으로 접기 위해 달성할 수 있는 레이저 작동 시간의 최솟값을 구하도록 도와주자.

패널을 펼쳤을 때 만들어지는 전지의 크기는 중요하지 않으며, 레이저 작동 시간만 최소화하면 된다.

첫 번째 줄에는 정수 t (1 ≤ t ≤ 1000)가 주어진다. 이는 테스트 쿼리의 수이다. 다음 t개의 줄에는 쿼리가 주어진다. 각 쿼리는 두 정수 n과 m (1 ≤ n, m ≤ 109)으로 이루어지며, 이는 태양 전지 원판의 처음 크기이다.

각 쿼리마다 과학자들이 달성할 수 있는 레이저 작동 시간의 최솟값을 한 줄에 하나씩 출력한다.