#P5970. [Usaco2022 Jan]Searching for Soulmates S

    ID: 4970 传统题 1000ms 256MiB 尝试: 2 已通过: 1 难度: 6 上传者: 标签>难度分类普及+/提高-贪心交换论证构造与建模逆向思考动态规划有限候选集缩减枚举与搜索暴力枚举CF1900

[Usaco2022 Jan]Searching for Soulmates S

题目描述

每头牛的性格由一个正整数表示。两头牛的性格值相同时,它们是灵魂伴侣。一次改变性格的操作可以将当前性格值乘以 22,除以 22(仅当当前值为偶数),或加 11。

Farmer John 给出 NN 对牛。对每一对,求只改变第一头牛的性格值,使它等于第二头牛所需的最少操作次数。

输入格式

第一行一个整数 NN(1≤N≤101\le N\le10)。接下来 NN 行,每行两个整数,依次给出两头牛最初的性格值。每个值在 [1,1018][1,10^{18}] 内。

输出格式

输出 NN 行,依次写出每对牛的最少操作次数。

样例 #1

样例输入 #1

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

样例输出 #1

8
3
8
3
0
20

样例解释 #1

第 11 组可以按 31→32→16→8→9→10→11→12→1331\to32\to16\to8\to9\to10\to11\to12\to13 改变性格。

第 22 组可以按 12→6→7→812\to6\to7\to8 改变性格。两条序列的操作次数均为相应组的最小值。

测试点性质

  • 测试点 1–4 的初始性格值均不超过 10510^5。
  • 测试点 5–12 无额外限制。