Largest Perfect Square with Prime Digit Sum

You are given a list of n integers. Your task is to find the largest number in the list that meets the following two conditions:

• The number is a perfect square (i.e. there exists an integer \(k\) such that \(k^2 = \text{number}\)).
• The sum of its digits is a prime number.

If no such number exists, output \(-1\). For example, if the input list is 16 25 36 49 50, the perfect squares with prime digit sums are 16 (digit sum = 7), 25 (digit sum = 7), and 49 (digit sum = 13). The answer in this case is 49 because it is the largest among them.

Note: The digit sum of a number is computed by adding all its decimal digits. A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself.

inputFormat

The input is read from stdin and consists of two lines. The first line contains a single integer (n), the number of elements in the array. The second line contains (n) space-separated integers.

outputFormat

Output a single integer to stdout: the largest perfect square from the list whose digit sum is a prime number. If no such number exists, output (-1).## sample

5
16 25 36 49 50

49