Collatz Conjecture

The Collatz conjecture is a fascinating phenomenon. The rule looks simple, yet it has still not been proven mathematically. In this problem we assume that the conjecture is always true.

The Collatz conjecture is defined as follows. Build a sequence of positive integers $x_i$ using these rules.

• If $x_i$ is even, then $x_{i+1} = x_i / 2$.
• If $x_i$ is odd, then $x_{i+1} = 3 \times x_i + 1$.

The conjecture states that such a sequence eventually reaches 1. Using computers, scientists have verified that the conjecture holds whenever the first term is smaller than $2^{58}$.

Now for the problem.

You are given two positive integers $A$ and $B$. Build a Collatz sequence from each of them. Comparing the two sequences from the beginning, find the first value $C$ that appears in both sequences, and determine at which position it appears in each sequence. Positions are counted with the first term as 0.

For convenience, a sequence stops as soon as it reaches 1 (after 1 the values would simply repeat as 1, 4, 2, 1, 4, 2, … forever).

The input consists of several test cases. Each test case contains two integers $A$ and $B$ ($1 \le A, B \le 1{,}000{,}000$). The last line contains two zeros and is not processed.

For each test case, print one line in the following format.

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

Here $C$ is the first value that appears in both the sequence of $A$ and the sequence of $B$, and $S_A$ and $S_B$ are the positions at which $C$ first appears in the sequence of $A$ and of $B$, respectively. Positions are counted with the first term as 0.