D. Заполни сумку
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У вас есть сумка размера $$$n$$$. Так же у вас есть $$$m$$$ коробок. Размер $$$i$$$-й коробки $$$a_i$$$, где $$$a_i$$$ — целая неотрицательная степень двойки.

Вы можете делить коробки на две части одинакового размера. Ваша задача — полностью заполнить сумку.

Например, если $$$n = 10$$$ и $$$a = [1, 1, 32]$$$, то вам нужно разделить коробку размера $$$32$$$ на две части размера $$$16$$$, а затем разделить коробку размера $$$16$$$. Таким образом, вы сможете заполнить сумку коробками размеров $$$1$$$, $$$1$$$ и $$$8$$$.

Посчитайте минимальное количество делений, которое придется сделать для заполнения сумки размера $$$n$$$.

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

Первая строка содержит число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных.

Первая строка каждого набора входных данных содержит два числа $$$n$$$ и $$$m$$$ ($$$1 \le n \le 10^{18}, 1 \le m \le 10^5$$$) — размер сумки и количество коробок, соответственно.

Вторая строка каждого набора входных данных содержит $$$m$$$ чисел $$$a_1, a_2, \dots , a_m$$$ ($$$1 \le a_i \le 10^9$$$) — размеры коробок. Гарантируется, что все $$$a_i$$$ — степени двойки.

Также гарантируется, что сумма всех $$$m$$$ по всем наборам входных данных не превосходит $$$10^5$$$.

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

На каждый набор входных данных выведите число — минимальное количество делений, которые придется сделать для заполнения сумки размера $$$n$$$ (или $$$-1$$$, если заполнить сумку невозможно).

Пример
Входные данные
3
10 3
1 32 1
23 4
16 1 4 1
20 5
2 1 16 1 8
Выходные данные
2
-1
0