Баш отправился в путешествие, чтобы стать величайшим мастером Покемонов. Чтобы получить первого покемона, он отправился в лабораторию профессора Зулу. Поскольку Баш — любимый студент профессора, Зулу разрешил ему взять столько покемонов из лаборатории, сколько Баш захочет.
Однако, профессор предупрел Баша, что группа из k > 1 покемонов с силами {s1, s2, s3, ..., sk} склонна к драке между собой, если gcd(s1, s2, s3, ..., sk) = 1 (смотрите примечания для определения gcd).
Баш, будучи умным студентом, не хочет, чтобы его покемоны дрались между собой. В то же время, он хочет максимизировать количество покемонов, которые он возьмет. Можете помочь Башу найти максимальное число покемонов, которых он может взять с собой?
Обратите внимание: Один покемон не может драться сам с собой.
Примечание
gcd (наибольший общий делитель) множества натуральных чисел {a1, a2, ..., an} равняется наибольшему натуральному числу, на которое делятся все числа {a1, a2, ..., an}.
В первом примере Баш может взять покемонов с силами {2, 4}, потому что gcd(2, 4) = 2.
Во втором примере Баш может взять покемонов с силами {2, 4, 6}, и не существует группы больше с gcd ≠ 1.