Гарні числа#7237
Школа №1331 в Ужляндії відома дуже високим рівнем знань своїх учнів з математики, тому що більшість учнів відвідують факультативні заняття відомого вчителя Антона Андрійовича.
Сьогодні Антон Андрійович розказав своїм учням про числа, які, на його думку, можуть володіти рядом цікавих властивостей. Він назвав такі числа гарними. Число називається гарним, якщо не існує такого цілого числа, більшого одиниці, на квадрат якого воно б ділилося без залишку. Наприклад, число не є гарним, тому що воно ділиться на , тобто на квадрат числа . Числа і є гарними числами.
Учні Антона Андрійовича дуже гарні в усному рахунку, тому в першому завданні необхідно було визначити: чи є деяке число гарним.
Однак, Марися, краща його учениця, швидко впоралась з цим завданням. Щоб якось її зайняти, вчитель написав на дошці чисел і дав їй нове завдання: визначити, чи є добуток цих чисел гарним числом. Дуже скоро Марися отримала відповідь, однак вона хоче перевірити себе. Тому вона просить Вас написати програму, яка перевіряє: чи є добуток чисел гарним числом, а якщо ні, то їй потрібно знати яке-небудь число, відмінне від одиниці, на квадрат якого ділиться добуток цих чисел.
Перший рядок вхідного файлу містить число (1 \le N \le 100) — кількість чисел, які вчитель написав на дошці для Марисі. Другий рядок містить натуральних чисел — самі числа. Кожне з чисел не перевершує 10^{18}.
Якщо число є гарним, виведіть єдиний рядок, що складається з слова Beautiful. Інакше, виведіть яке-небудь число, відмінне від одиниці, на квадрат якого ділиться добуток чисел.
Приклад 1
Перший приклад: 5 \cdot 6 \cdot 7 = 210. Не існує числа, більшого за одиницю, на квадрат якого ділилось би без залишку, тому — гарне число.
Другий приклад: 35 \cdot 12 = 420. ділиться на , тобто на квадрат числа .
A_1 \cdot A_2 \cdot \ldots \cdot A_N \le 10^6 — не менше балів
A_1 \cdot A_2 \cdot \ldots \cdot A_N \le 10^{12} — не менше балів
Для усіх : A_i \le 10^{12} — не менше балів