Очень длинный забор
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
64 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Петя хочет построить длинный забор. Он уже нашел хорошее место, чтобы построить его, и все, что остается — это собрать необходимые материалы.

В местном магазине продают доски всего n разных длин, однако досок каждого типа можно купить сколько угодно. Чтобы избежать отходов, Петя хочет, чтобы общая длина этих досок была в точности равна длине забора l.

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

Будьте готовы, забор будет очень длинный!

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

Первая строка входного файла содержит количество тестов t, Далее следуют описания тестов.

Каждый тест состоит из двух строк. Первая строка содержит два целых числа l и n — общую длину забора и количество различных длин досок, которые можно купить. Вторая строка n целых чисел b1,b2, ...,bn — возможные длины досок.

Ограничения: 1 ≤t≤ 50, 1010≤l≤ 1018.

В задаче 1: 1 ≤bi≤ 100.

В задаче 2: 1 ≤bi≤ 100000.

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

Для каждого теста выведите минимальное число досок, необходимых для того, чтобы построить забор. Если построить забор невозможно, выведите - 1.

Примеры тестов

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

    2
    10000000001 3
    23 51 100
    10000000001 3
    100 52 22

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

    100000004
    -1

Примечание

В первом примере нужно взять 2 доски длиной 23, 5 досок длиной 51 и 99999997 досок длиной 100. Конечно, можно было бы использовать только 100000001 доску длиной 100, но тогда длина будет больше l.

Во втором примере можно получить только четные длины.