您正在开发一个测试生成器。它需要两个整数 $$$s$$$ 和 $$$m$$$ 作为输入。您需要构造一个非负整数数组 $$$a = [a_{1}, a_{2}, \dots, a_{n}]$$$ ,这样:
- $$$\displaystyle\sum_{i=1}^{n} a_i = s$$$;
- 对于每个 $$$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$$$ 的最小可能值 — 数组的长度。
示例
输入复制
613 513 313 61000000007 277664899999999999 1998244353 1557287
输出复制
35-1-199999999999642
注意
我们来分析一些例子:
- 对于$$$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$$$,因为没有合适的数组。