题目大意

我们有两个非负整数 $x$ 和 $y$。

你可以执行任意多次（包括零次）以下操作：选择一个正整数 $k$，然后将 $x$ 或 $y$ 中的一个替换为 $\left\lfloor \frac{\text{那个数}}{2k} \right\rfloor$，本次操作的成本为 $2k$。
但有一个额外的约束：你不能选择同一个 $k$ 超过一次。

你的任务是计算使 $x = y$ 所需的最小可能总成本。

---

关键观察

1. 除法运算的合并

对于任意正整数 $x$，以下等式成立：

$$\left\lfloor \frac{\lfloor x / 2^a \rfloor}{2^b} \right\rfloor = \left\lfloor \frac{x}{2^{a+b}} \right\rfloor $$

这意味着：对一个数多次除以 $2$ 的不同幂次，等价于除以这些幂次之和的 $2$ 的幂。
因此，我们只关心每个数总共除以 $2$ 的多少次方，而不关心除法的顺序。

2. 操作的本质

令：

• $x$ 被除的总次数为 $i$（即总共除以 $2^i$）
• $y$ 被除的总次数为 $j$（即总共除以 $2^j$）

那么操作后：

$$x' = \left\lfloor \frac{x}{2^i} \right\rfloor, \quad y' = \left\lfloor \frac{y}{2^j} \right\rfloor $$

并且要求 $x' = y'$。

3. 约束条件

由于不能重复使用同一个 $k$，并且题目中的操作是除以 $2k$，但经过分析（或根据标程的简化），我们可以将问题等价为：
每次选择一个 $2$ 的幂 $2^p$（$p \ge 0$），将其分配给 $x$ 或 $y$，表示该数除以 $2^p$，成本为 $2^p$，每个 $p$ 只能用一次。

这样，$x$ 总共除以 $2^i$，$y$ 总共除以 $2^j$，其中 $i$ 和 $j$ 分别是分配给 $x$ 和 $y$ 的幂次之和，且用过的幂次两两不同。

---

动态规划

因为 $x, y \le 10^{17} < 2^{60}$，所以 $i, j \le 60$。
定义 $dp[i][j]$ = 用一些不同的 $2$ 的幂（每个幂只能用一次），使得 $x$ 获得的总指数为 $i$，$y$ 获得的总指数为 $j$，所需的最小总成本。

初始状态：$dp[0][0] = 0$，其余为无穷大。

考虑幂 $2^p$（$p = 0, 1, \dots, 59$），我们可以：

• 不使用这个幂
• 分配给 $x$，则 $i \to i + p$，成本增加 $2^p$
• 分配给 $y$，则 $j \to j + p$，成本增加 $2^p$

由于每个幂只能用一次，按 $p$ 从小到大更新，且需要倒序更新 $i, j$（类似 0-1 背包），以防止重复使用同一个幂。

---

查询答案

对于给定的 $x, y$，我们要找到 $i, j$ 使得：

$$\left\lfloor \frac{x}{2^i} \right\rfloor = \left\lfloor \frac{y}{2^j} \right\rfloor $$

并且 $dp[i][j]$ 最小。

注意：$x$ 右移 $i$ 位（整数除法）就是 $\lfloor x / 2^i \rfloor$。
所以条件等价于：

$$(x >> i) = (y >> j)$$

枚举所有 $i, j \in [0, 60)$，检查上述等式，取最小的 $dp[i][j]$。

---

最终答案

对每个测试用例，输出：

$$\min_{0 \le i,j < 60,\; (x>>i) = (y>>j)} dp[i][j]$$

若 $x = y$，则 $i = j = 0$ 即可，$dp[0][0] = 0$。

---

复杂度

• DP 预计算：$O(B^3) = O(60^3) = O(216000)$，非常小
• 每个查询：$O(B^2) = O(3600)$，$t$ 最大 $10^5$，总约 $3.6 \times 10^8$ 次操作，在 3.5 秒内可行（使用 C++ 优化可通过）

---

总结

这道题的核心是：

1. 注意到除以 $2$ 的幂可以合并。
2. 将问题转化为：给 $x$ 和 $y$ 分配不同的 $2$ 的幂作为除数，使得最终值相等，并最小化总成本。
3. 用 0-1 背包 DP 预计算所有可能分配的最小成本。
4. 查询时枚举 $i, j$ 检查相等条件，取最小值。