Во новиот истражувачки центар на Факултетот за информатички науки и компјутерско инженерство (ФИНКИ), асистентот по информатика Илија кој држел вежби во лабораторија бр. 9 бил живо заинтересиран и преокупиран со бројот 9 и неговиот однос со другите броеви.

Еден ден, тој на своите студенти на час им дал една "лесна" задача за решавање. Тој им рекол дека од било кој број N во конечен број на чекори може да добијат број делив со 9, така што ќе се соберат цифрите на бројот N (нека го означиме збирот со Z) и тој збир Z во секој чекор ќе го додаваме на самиот број. На пример, ако бројот е N=255, Z=2+5+5=12, новиот број е N+Z=255+12=267 кој не е делив со 9, па значи 267+Z=267+12 итн. Илија всушност го интересира после колку чекори даден број ќе стане делив со 9, и ниту еден друг меѓурезултат. За студентите ова било многу лесно, тие ја решиле задачата за неколку минутки и чекале Илија да им напише број на табла. Илија, сакајќи да ги надмудри, го напишал бројот

        3141592653589793238462643383279502884197169399375


Повторно ги оставил да размислуваат. По дваесет минути, најдобриот студент во групата го дал решението. Тој му одговорил на Илија дека се потребни само два чекора.

Илија му рекол на студентот да не им го дава алгоритамот на своите колеги и секој од студентите наредниот час да дојде со решение. Студентите ве молат за помош околу програмата. Помогнете им, затоа што кога се работи за бројот 9, кај Илија не се поминува лесно!

Влез

Во првата и единствена линија е запишан почетниот број N (1 ≤ N < 10⁸⁰). Бројот е запишан стандардно - на почетокот или крајот од линијата нема непотребни празни места. N е цел број.

Излез

Да се испечати бројот на чекори по кој ќе се добие број делив со 9.

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

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

Примери

влез
9

излез
0

влез
12

излез
2

влез
3141592653589793238462643383279502884197169399375

излез
2

Објаснување за вториот пример: 12+(1+2) = 15, па 15+3 = 18. Сега, 18 е број делив со 9 и тука запираме. Забележете дека, во секој чекор, го додаваме збирот на цифрите на почетниот број N - во овој случај, додаваме 1+2=3.