Masha and the Candies
Masha loves chocolate candies in boxes—they're delicious, attractive, and perfect for sharing with friends. However, sharing can sometimes be tricky: if the number of candies in a box doesn't divide evenly among everyone, someone might end up with fewer candies, or there might be leftovers. To avoid this, Masha wants to buy boxes with a number of candies that can be divided by the greatest number of prime divisors.
For instance, Masha would choose a box with 30 candies over one with 40 candies because 30 has three prime divisors (2, 3, and 5), whereas 40 has only two (2 and 5).
Your task is to write a program for Masha. She will use this program in the store to select the most suitable box from the entire assortment, based on the number of candies that can be divided by the largest number of prime divisors.
Input
The first line contains the number n (n ≤ 1024), representing the different candy boxes available in the store. The following lines contain exactly n numbers, each ranging from 2 to 1024. These numbers indicate the count of candies in each box. The numbers are separated by spaces and may also be separated by newline characters.
Output
Output the number of candies in the box that can be divided by the maximum number of prime numbers. If there are multiple options, choose the smallest number, as Masha prefers to buy smaller boxes.