C. Test Generator
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

You are developing a test generator. It takes two integers $$$s$$$ and $$$m$$$ as input. You need to construct an array of non-negative integers $$$a = [a_{1}, a_{2}, \dots, a_{n}]$$$ such that:

  1. $$$\displaystyle\sum_{i=1}^{n} a_i = s$$$;
  2. for each $$$i$$$, the condition $$$a_i \,\&\, m = a_i$$$ holds, where $$$\&$$$ denotes the bitwise AND operator.

In other words, in each number $$$a_i$$$, the bits that are set to one can only be in the positions where the bits in the number $$$m$$$ are also set to one.

Determine whether there exists at least one such array. If it exists, find the minimum possible length $$$n$$$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

Each test case consists of a single line containing two integers $$$s$$$ and $$$m$$$ ($$$1 \le s, m \le 10^{18}$$$) — parameters of the generator.

Output

For each test case, print one integer:

  • if such an array does not exist, print $$$-1$$$;
  • otherwise, print the minimum possible value of $$$n$$$ — the length of the array.
Example
Input
6
13 5
13 3
13 6
1000000007 2776648
99999999999 1
998244353 1557287
Output
3
5
-1
-1
99999999999
642
Note

Let's analyze some examples:

  • For $$$s = 13, m = 5$$$, the answer is $$$3$$$, as there is a suitable array $$$a = [5, 4, 4]$$$;
  • For $$$s = 13, m = 3$$$, the answer is $$$5$$$, as there is a suitable array $$$a = [3, 3, 3, 3, 1]$$$;
  • For $$$s = 13, m = 6$$$, the answer is $$$-1$$$, as there is no suitable array.