Beautiful Numbers#7237
School No. 1331 in Uzhlia is famous for its students' exceptional mathematical skills, largely due to the extracurricular classes taught by the renowned teacher, Anton Andriyovych.
Today, Anton Andriyovych introduced his students to numbers he believes have intriguing properties, which he calls beautiful numbers. A number is considered beautiful if there is no integer greater than one whose square divides it evenly. For instance, is not beautiful because it is divisible by , the square of . However, and are beautiful numbers.
The students are adept at mental calculations, so their initial task was to determine if a given number is beautiful.
Marisia, the top student, quickly solved this problem. To challenge her further, the teacher wrote numbers on the board and tasked her with determining whether the product of these numbers is a beautiful number. Marisia soon found the answer but wants to verify it. She asks you to create a program that checks if the product of these numbers is beautiful. If it is not, she needs to know any number greater than one whose square divides the product.
The first line contains the integer (1 \le N \le 100), representing the number of numbers written on the board. The second line contains natural numbers. Each number does not exceed 10^{18}.
If the product is beautiful, output Beautiful on a single line. Otherwise, output any number greater than one whose square divides the product of the numbers.
Example 1
First example: 5 \cdot 6 \cdot 7 = 210. There is no integer greater than one whose square divides evenly, so is a beautiful number.
Second example: 35 \cdot 12 = 420. The number is divisible by , which is the square of .
A_1 \cdot A_2 \cdot \ldots \cdot A_N \le 10^6 — at least points
A_1 \cdot A_2 \cdot \ldots \cdot A_N \le 10^{12} — at least points
For all : A_i \le 10^{12} — at least points