콜라츠 추측

콜라츠 추측은 흥미로운 현상이다. 규칙은 단순해 보이지만 아직 수학적으로 증명되지 않은 문제이다. 이 문제에서는 콜라츠 추측이 항상 참이라고 가정한다.

콜라츠 추측은 다음과 같다. 양의 정수로 이루어진 수열 $x_i$를 아래 규칙으로 만든다.

• $x_i$가 짝수이면 $x_{i+1} = x_i / 2$
• $x_i$가 홀수이면 $x_{i+1} = 3 \times x_i + 1$

콜라츠 추측은 이렇게 만든 수열이 언젠가 반드시 1에 도달한다는 것이다. 과학자들은 컴퓨터를 이용해 첫 항이 $2^{58}$보다 작으면 이 추측이 참임을 확인했다.

이제 문제를 살펴보자.

양의 정수 두 개 $A$와 $B$가 주어진다. 두 수 각각에 대해 위 규칙으로 콜라츠 수열을 만든다. 두 수열을 앞에서부터 비교했을 때 두 수열에 공통으로 처음 나타나는 값 $C$를 찾고, 그 값이 각 수열에서 몇 번째 위치에 있는지 구한다. 위치는 첫 항을 0으로 세어 계산한다.

편의를 위해 수열은 값이 1이 되면 더 이상 진행하지 않는다. (1 이후에는 1, 4, 2, 1, 4, 2, …가 끝없이 반복되기 때문이다.)

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 두 정수 $A$와 $B$로 구성된다 ($1 \le A, B \le 1{,}000{,}000$). 입력의 마지막 줄은 두 개의 0으로 이루어지며, 이 줄은 처리하지 않는다.

각 테스트 케이스마다 다음 형식의 문장을 한 줄에 출력한다.

A needs SA steps, B needs SB steps, they meet at C

여기서 $C$는 $A$의 수열과 $B$의 수열에 공통으로 처음 나타나는 값이고, $S_A$와 $S_B$는 각각 $A$의 수열과 $B$의 수열에서 $C$가 처음 나타나는 위치이다. 위치는 첫 항을 0으로 세어 계산한다.