#USACOC2223A. Searching for Soulmates

Searching for Soulmates

Description

Farmer John's cows each want to find their soulmate -- another cow with similarcharacteristics with whom they are maximally compatible. Each cow's personality is described by an integer pip_i. Two cows with the same personality are soulmates.A cow can change her personality via a "change operation" by multiplying by 22,dividing by 22 (if pip_i is even), or adding 11.

Farmer John initially pairs his cows up in an arbitrary way. He is curious howmany change operations would be needed to make each pair of cows into soulmates.For each pairing, decide the minimum number of change operations the first cowin the pair must make to become soulmates with the second cow.

  • 1pi10181 \leq p_i \leq 10^{18}

Input Format

The first line contains NN, the number of pairs of cows. Eachof the remaining NN lines describes a pair of cows in terms of two integersgiving their personalities. The first number indicates the personality of thecow that must be changed to match the second.

  • 1N101\le N\le 10

Output Format

Please write NN lines of output. For each pair, print the minimum number ofoperations required for the first cow to make her personality match that of thesecond.

6
31 13
12 8
25 6
10 24
1 1
997 120
6
31 13
12 8
25 6
10 24
1 1
997 120

Scoring

  • Test cases 1-4 satisfy pi105p_i \le 10^5.
  • Test cases 5-12 satisfy no additional constraints.

Problem Credit

Problem credits: Quanquan Liu