У Бесси действительно много друзей, потому что она — всеми любимая корова! Ее новый друг Кролик пытается допрыгать до Бесси, чтобы поиграть вместе!
Точнее, он хочет попасть из \((0,0)\) в \((x,0)\), сделав несколько прыжков. Он готов прыгнуть из одной точки в другую на плоскости только если евклидово расстояние между этими точками равно одному из \(n\) его любимых чисел: \(a_1, a_2, \ldots, a_n\). За какое минимальное количество прыжков Кролик сможет добраться из \((0,0)\) в \((x,0)\)? Кролик может приземляться, в том числе, и в точки с нецелочисленными координатами. Можно доказать, что Кролик всегда может достигнуть точки назначения.
Напомним, что евклидово расстояние между точками \((x_i, y_i)\) и \((x_j, y_j)\) равно \(\sqrt{(x_i-x_j)^2+(y_i-y_j)^2}\).
Например, если любимые числа Кролика — это \(1\) и \(3\), то он может добраться из \((0,0)\) в \((4,0)\) за два прыжка (как показано ниже). Заметим, что существуют и другие способы добраться до \((4,0)\) за \(2\) прыжка (например, \((0,0)\) \(\rightarrow\) \((2,-\sqrt{5})\) \(\rightarrow\) \((4,0)\)).
Изображение соответствует первому набору входных данных из примера. Длина обоих прыжков равна \(3\), одному из любимых чисел Кролика. Таким образом, перед каждым прыжком Кролик выбирает одно из чисел \(a_i\) и прыгает из текущей точки на расстояние ровно \(a_i\) в произвольном направлении. Одно и то же число он может выбирать любое количество раз.
Выходные данные
Для каждого набора входных данных выведите единственное число — минимальное необходимое количество прыжков.
Примечание
Первый набор изображен на рисунке выше. Кролик может прыгнуть сначала в \((2,\sqrt{5})\), а потом в \((4,0)\) — суммарно два прыжка. Каждый прыжок имеет длину \(3\) — одно из его любимых чисел.
Во втором наборе, одним из способов добраться за \(3\) прыжка является: \((0,0)\) \(\rightarrow\) \((4,0)\) \(\rightarrow\) \((8,0)\) \(\rightarrow\) \((12,0)\).
В третьем наборе, Кролик может прыгнуть из \((0,0)\) в \((5,0)\).
В четвертом наборе, Кролик может прыгать так: \((0,0)\) \(\rightarrow\) \((5,10\sqrt{2})\) \(\rightarrow\) \((10,0)\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
2 4
1 3
3 12
3 4 5
1 5
5
2 10
15 4
|
2
3
1
2
|