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:

$$$\displaystyle\sum_{i=1}^{n} a_i = s$$$;
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.

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.

Test Generator

Examples