CF2203C Test Generator

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 $ .

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.

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.

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.