Сновида

У президента Першого нацiонального банку майора Томаса Б. Кiнгмена (героя оповiдання О'Генрi "Товаришi iз Сан-Розарiо") з'явилася шкідлива звичка щоночi перекладати однаковим чином вмiст сейфiв, у яких клiєнти зберiгають свої коштовностi.

Створiть програму, яка допоможе вирахувати, через скiльки дiб всi коштовностi вперше повернуться на свої мiсця.

Вхідні дані

Перший рядок мiстить кiлькiсть сейфiв n банку, що не перевищує 15500. Далi (починаючи з другого рядка) мiститься послiдовнiсть n рiзних натуральних чисел в межах вiд 1 до n включно. k-ий член цiєї послiдовностi - номер сейфу, куди майор перекладає вмiст k-го сейфу першої ночi.

Вихідні дані

Мiстить запис у десятковiй системi числення шуканого числа дiб, що містить не більше ніж 1000 цифр.

Приклади