C. Медуза и зеленое яблоко
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У медузы есть $$$n$$$ кусочков зеленого яблока. Каждый кусочек весит $$$1~\text{кг}$$$. Медуза хочет разделить эти кусочки зеленого яблока поровну между $$$m$$$ людьми.

У Медузы есть волшебный нож. Каждый раз Медуза может выбрать один кусок зеленого яблока и разделить его на два меньших куска, причем каждый кусок будет иметь массу, равную половине массы исходного куска.

Медуза хочет узнать минимальное количество операций, необходимых для того, чтобы она могла разделить кусочки зеленого яблока так, чтобы общий вес кусочков яблока, полученных каждым человеком, был одинаковым.

Входные данные

Каждый тест содержит несколько наборов входных данных. В первой строке указано количество наборов входных данных $$$t$$$ ($$$1 \leq t \leq 2 \cdot 10^4$$$). Далее следует описание наборов входных данных.

Первая и единственная строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \leq n, m \leq 10^9$$$) — количество исходных кусочков зеленого яблока и количество людей.

Выходные данные

Для каждого набора входных данных выведите одно целое число — минимальное количество операций, необходимых для того, чтобы разделить все зеленые яблоки поровну между $$$m$$$ людьми. Если это невозможно сделать с помощью конечного числа операций, то вместо этого выведите $$$-1$$$.

Пример
Входные данные
4
10 5
1 5
10 4
3 4
Выходные данные
0
-1
2
5
Примечание

В первом наборе входных данных нам не нужно делить кусочки яблок. Каждый человек получит $$$2$$$ кусочка по $$$1~\text{кг}$$$, а общий вес кусочков яблок, полученных каждым человеком, составит $$$2~\text{кг}$$$.

Во втором наборе входных данных разделить яблоки поровну с помощью конечного числа операций невозможно.

В третьем наборе входных данных мы можем разделить два яблока массой $$$1~\text{кг}$$$, получив $$$4$$$ кусочка массой $$$0,5~\text{кг}$$$. Каждый человек получит $$$1$$$ кусочек яблока массой $$$0,5~\text{кг}$$$ и $$$2$$$ кусочка яблока массой $$$1~\text{кг}$$$. Общий вес кусочков яблок, полученных каждым человеком, составляет $$$2,5~\text{кг}$$$.

В четвертом наборе входных данных сначала делим все $$$3$$$ кусочка массой $$$1~\text{кг}$$$, получая $$$6$$$ кусочков массой $$$0,5~\text{кг}$$$. Затем еще разделим два кусочка массой $$$0,5~\text{кг}$$$, получив $$$4$$$ кусочка массой $$$0,25~\text{кг}$$$. Каждый человек получит $$$1$$$ кусочек яблока массой $$$0,5~\text{кг}$$$ и $$$1$$$ кусочек яблока массой $$$0,25~\text{кг}$$$. Общий вес яблок, полученных каждым человеком, составляет $$$0,75~\text{кг}$$$.