Гарні числа#80

Гарні числа

Школа №1331 в Ужляндії відома дуже високим рівнем знань своїх учнів з математики, тому що більшість учнів відвідують факультативні заняття відомого вчителя Антона Андрійовича.

Сьогодні Антон Андрійович розказав своїм учням про числа, які, на його думку, можуть володіти рядом цікавих властивостей. Він назвав такі числа гарними. Число називається гарним, якщо не існує такого цілого числа, більшого одиниці, на квадрат якого воно б ділилося без залишку. Наприклад, число 12 не є гарним, тому що воно ділиться на 4, тобто на квадрат числа 2. Числа 13 і 14 є гарними числами.

Учні Антона Андрійовича дуже гарні в усному рахунку, тому в першому завданні необхідно було визначити: чи є деяке число гарним.

Однак, Маріся, краща його учениця, швидко впоралась з цим завданням. Щоб якось її зайняти, вчитель написав на дошці N чисел і дав їй нове завдання: визначити, чи є добуток цих чисел гарним числом. Дуже скоро Маріся отримала відповідь, однак вона хоче перевірити себе. Тому вона просить Вас написати програму, яка перевіряє: чи є добуток чисел гарним числом, а якщо ні, то її потрібно знати яке-небудь число, відмінне від одиниці, на квадрат якого ділиться добуток цих чисел.

Input

Перший рядок вхідного файлу містить число (1 \leq N \leq 100) — кількість чисел, які вчитель написав на дошці для Марісі. Другий рядок містить натуральних чисел — самі числа. Кожне з чисел не перевершує 10^{18}.

Output

Якщо число є гарним, виведіть єдиний рядок, що складається з слова Beautiful. Інакше, виведіть яке-небудь число, відмінне від одиниці, на квадрат якого ділиться добуток чисел.

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading

Note

Перший приклад: 5*6*7 = 210. Не існує числа, більшого за одиницю, на квадрат якого 210 ділилось би без залишку, тому 210 — гарне число.

Другий приклад: 35*12 = 420. 420 ділиться на 4, тобто на квадрат числа 2.

Scoring

A_1 * A_2 * \ldots * A_N \leq 10^6 — не менше 20 балів

A_{1} * A_{2} * \ldots * A_{N} \leq 10^{12} — не менше 40 балів

Для усіх : A_{i} \leq 10^{12} — не менше 60 балів