#USACOC2223A. Searching for Soulmates

Searching for Soulmates

题目描述

Farmer John 的每头奶牛都想找到她们的灵魂伴侣——另一头具有相似特点的奶牛,与她们最大程度地相容。每头奶牛的性格由一个整数 pip_i 描述。两头性格相同的奶牛就是灵魂伴侣。奶牛可以通过「改变操作」,对她的性格乘以 22,除以 22(当 pip_i 是偶数时),或者加上 11

Farmer John 最初以任意方式配对了他的奶牛。他很好奇为使每对奶牛成为灵魂伴侣需要进行多少次改变操作。对于每对奶牛,求配对中的第一头奶牛所必须进行的最小改变操作次数,从而可以与第二头奶牛成为灵魂伴侣。

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

输入格式

输入的第一行包含 NN,为奶牛配对的数量。以下 NN 行每行描述了一对奶牛,包含两个整数,为她们的性格值。第一个整数是需要被改变与另一头奶牛相匹配的奶牛的性格。

  • 1N101\le N\le 10

输出格式

输出 NN 行。对于每一对奶牛,输出第一头奶牛需要进行的最小操作次数,使得她的性格与第二头奶牛相匹配。

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

测试点性质

  • 测试点 1-4 满足 pi105p_i \le 10^5
  • 测试点 5-12 没有额外限制。

题目提供者

供题:Quanquan Liu