Masha and the Candies#2239
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 candies over one with candies because has three prime divisors (, , and ), whereas has only two ( and ).
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.
The first line contains the number (n \leq 1024), representing the different candy boxes available in the store. The following lines contain exactly numbers, each ranging from to . 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 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.
Example 1