정수 놀이

우니는 오늘 학교에서 양의 정수에 대해 배웠다.

에띠는 우니에게 다음과 같은 네 가지 연산을 가르쳐주었다.

• 양의 정수에 1을 더한다. (즉, $X := X+1$)
• 양의 정수에서 1을 뺀다. (즉, $X := X-1$)
• 양의 정수에 자기 자신을 곱한다. (즉, $X := X \times X$)
• 양의 정수 $X$가 있을 때, $Y \times Y = X$인 양의 정수 $Y$가 존재한다면, 그 값으로 바꾼다. (즉, $X := \sqrt{X}$)

단, 연산 이후 결과가 양의 정수가 되는 경우에만 연산을 할 수 있다.

네 가지 연산을 가르쳐 준 이후 에띠는 우니에게 이런 질문을 했다.

양의 정수 $A$에 네 가지 연산을 적절히 하여 양의 정수 $B$를 만들 때, 필요한 최소 연산 횟수는 몇 번일까?

우니를 도와 에띠가 물은 질문에 답을 하는 프로그램을 작성하시오.

입력 형식

첫 줄에 에띠가 한 질문의 수를 나타내는 정수 $Q$가 주어진다. $(1 \le Q \le 100\,000)$

이어지는 $Q$ 개의 줄의 각 줄에 질문에 대한 정보를 나타내는 두 정수 $A$와 $B$가 공백으로 구분되어 주어진다. $(1 \le A, B \le 1\,000\,000\,000\,000\,000\,000)$

출력 형식

$i$ 번째 줄에 $i$ 번째 질문에 대한 답을 출력한다.

예제

3
12 34
35 2
100 101

9
5
1

예제 설명

첫 번째 질문에서, $12$ $\Rightarrow 11$ $\Rightarrow 10$ $\Rightarrow 9$ $\Rightarrow 8$ $\Rightarrow 7$ $\Rightarrow 6$ $\Rightarrow 36$ $\Rightarrow 35$ $\Rightarrow 34$와 같이 연산하면, $12$에 $9$ 번의 연산을 하여 $34$를 만들 수 있다.

두 번째 질문에서, $35$ $\Rightarrow 36$ $\Rightarrow 6$ $\Rightarrow 5$ $\Rightarrow 4$ $\Rightarrow 2$와 같이 연산하면, $35$에 $5$ 번의 연산을 하여 $2$를 만들 수 있다.

채점 방식

입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞혀야 그 종류에 배정된 점수를 받을 수 있다.

해설