C. Генератор тестов
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вы разрабатываете генератор тестов. На вход ему подаются целые числа $$$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$$$, где $$$\&$$$ — оператор побитового И.

Иными словами, в каждом числе $$$a_i$$$ единицы могут стоять только в тех битах, где единицы стоят и в числе $$$m$$$.

Определите, существует ли хотя бы один такой массив. Если существует, найдите минимально возможную длину $$$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$$$, так как не существует подходящего массива.