Задача 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 |