На екрані комп'ютера було записано число 123456789. Вася так вставив пробіли між деякими цифрами цього числа, що воно розбилося на кілька частин, причому числа, записані в будь-яких двох частинах, виявилися взаемно простими. Яка найбільша кiлькiсть частин могла при цьому утворитися? (Нагадаємо, що взаемно простими називаються натуральні числа, у яких є рівно один спільний дільник - одиниця)

Зауважимо, що з чотирьох парних цифр: 2, 4, 6 і 8 цілий шматок може скласти не більше ніж одна. Решта три зобов'язані увійти в шматки, що складаються з двох і більше цифр( причому увійти в шматки не в якості останньої цифри). Це означає, що шматків не може бути більше шести (три шматки по дві цифри і три шматки по одній цифрі).

Один з можливих прикладів розбиття даного шматка на шість шматків: 1 23 4 5 67 89.

Відповідь: шість