싱치우의 장난

행추가 다시 한번 충운의 아이스크림을 이상한 자물쇠가 달린 상자에 숨겼다. 리월의 여름은 늘 덥고, 충운은 넘치는 양(陽) 기운 때문에 더 힘들어해서 그 아이스크림이 꼭 필요하다.

Pixiv ID: 86787400

자물쇠에는 두 정수 $a$와 $b$가 적혀 있다. 충운은 다음 세 가지 연산을 원하는 만큼 몇 번이든 수행할 수 있다.

• $a$와 $b$에서 각각 1을 뺀다.
• $a$와 $b$에 각각 1을 더한다.
• $a$와 $b$를 둘 다 나누는 소수 $g$로 나눈다.

$a$ 또는 $b$ 중 하나 또는 둘 모두가 1이 되면 상자가 열린다. 충운이 아이스크림을 최대한 빨리 되찾을 수 있도록, 상자를 여는 데 필요한 연산 횟수의 최솟값을 구하시오.

첫 줄에 테스트 케이스의 개수 $T$ ($1 \le T \le 300$)가 주어진다. 각 테스트 케이스는 한 줄로 이루어지며, 정수 $a$와 $b$ ($1 \le a, b \le 10^9$, $a \ne b$)가 주어진다.

각 테스트 케이스마다 $a$, $b$, 또는 둘 모두를 1로 만드는 데 필요한 최소 연산 횟수를 한 줄에 출력한다.

첫 번째 테스트 케이스의 최적 방법은 $(4, 7) \rightarrow (3, 6) \rightarrow (1, 2)$이다.

두 번째 테스트 케이스의 최적 방법은 첫 번째 연산을 7번 적용하는 것이다.

세 번째 테스트 케이스의 최적 방법은 $(32, 84) \rightarrow (16, 42) \rightarrow (15, 41) \rightarrow (14, 40) \rightarrow (13, 39) \rightarrow (1, 3)$이다.

네 번째 테스트 케이스의 최적 방법은 $(11, 35) \rightarrow (12, 36) \rightarrow (6, 18) \rightarrow (2, 6) \rightarrow (1, 3)$이다.