Една телефонска компанија понудила пакет услуги за професорите од Криптографија. Меѓутоа, цената ја скрила во стринг S (низа од цифри од 1 до 9).

Професорите го добиле стрингот, а знаат и дека се работи за цена пониска од 1 000 000, која исто така е прост број.

Утврдете колку можни различни тарифи односно цени (според горните услови) има во стрингот.

Влез

Во првиот ред е даден стринг од цифри S. Должината на S е најмногу 1 000 000.

Забелешка:
За 30% од поените, должината на S е најмногу 10 000.
За дополнителни 35% од поените, должината на S е најмногу 100 000.

Излез

Отпечатете еден цел број - бројот на различни тарифи кои ги има во стрингот.

Ограничувања

Временско ограничување: 500 milliseconds
Мемориско ограничување: 64 megabytes

Примери

влез
15293

излез
5

влез
3292

излез
3

Објаснување за првиот пример: Прости броеви се: 2, 3, 5, 29, 293.

Објаснување за вториот пример: Прости броеви се: 2, 3 и 29.