Задача Train2020.  Укрзалізниця активно розширює міжнародне сполучення. Для збільшення кількості маршрутів було придбано надсучасні поїзди класу Інтерсіті++. Пробна серія включала рівно один локомотив (з номером 1) та N-1 вагон з номерами від 2 до N.

Після придбання було виявлено, що особливості будови механізму зчеплення вагонів дозволяють зчіплювати лише ті вагони, номери яких мають спільний дільник, відмінний від одиниці. Виключення стосується лише локомотива - він може бути причеплений лише попереду потяга і має можливість зчепитися з будь-яким вагоном.

Від кількості вагонів у рухомому складі залежить прибуток компанії, а тому керівництво просить вас про допомогу - визначити максимальну кількість вагонів (з урахуванням локомотива), які можна сполучити послідовно у рухомий склад.

 

Технічні умови Програма Train2020 зчитує з пристрою стандартного введення єдине число N - кількість отриманих вагонів (N≤105). Програма повинна виводити рівно одне число - максимальну довжину рухомого складу.

Приклади

Введення

Виведення

Коментар

3

2

Вагони 2 та 3 сполучити не можна, а тому рухомий склад буде або 1-2,

або ж 1-3

6

5

Можливий варіант рухомого складу наступний:

1-2-4-6-3

 

© LIKT 1998-2018