← 返回题目列表

Codeforces · 2203/C

C. 测试发生器

中文机器翻译题面 查看原题

您正在开发一个测试生成器。它需要两个整数 $$$s$$$ 和 $$$m$$$ 作为输入。您需要构造一个非负整数数组 $$$a = [a_{1}, a_{2}, \dots, a_{n}]$$$ ,这样:

  1. $$$\displaystyle\sum_{i=1}^{n} a_i = s$$$;
  2. 对于每个 $$$i$$$,条件 $$$a_i \,\&\, m = a_i$$$ 成立,其中 $$$\&$$$ 表示按位 AND 运算符。

换句话说,在每个数字$$$a_i$$$中,被设置为1的位只能位于数字$$$m$$$中的位也被设置为1的位置。

判断是否存在至少一个这样的数组。如果存在,求最小可能长度$$$n$$$。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例由一行组成,其中包含两个整数 $$$s$$$ 和 $$$m$$$ ($$$1 \le s, m \le 10^{18}$$$) - 生成器的参数。

输出

对于每个测试用例,打印一个整数:

  • 如果这样的数组不存在,则打印$$$-1$$$;
  • 否则,打印 $$$n$$$ 的最小可能值 — 数组的长度。

示例

输入
复制

6
13 5
13 3
13 6
1000000007 2776648
99999999999 1
998244353 1557287

输出
复制

3
5
-1
-1
99999999999
642

注意

我们来分析一些例子:

  • 对于$$$s = 13,m = 5$$$,答案是$$$3$$$,因为有一个合适的数组$$$a = [5, 4, 4]$$$;
  • 对于 $$$s = 13, m = 3$$$,答案是 $$$5$$$,因为有一个合适的数组 $$$a = [3, 3, 3, 3, 1]$$$;
  • 对于$$$s = 13,m = 6$$$,答案是$$$-1$$$,因为没有合适的数组。