Pinocchio spune în fiecare zi de lucru a săptămânii câte o minciună. Bunicul Gepetto ştie despre acest obicei urât, dar mai ştie şi că Pinocchio îşi notează minciunile şi le ţine ascunse într-un sipet. Pentru a nu uita cifrul de deschidere al sipetului, acesta şi-a notat algoritmul într-un carneţel, pe care l-a uitat lângă sipet. Bunicul Gepetto l-a găsit din întamplare şi a văzut notat in carneţel, pe primul rând, un număr natural notat a. Pe rândul al doilea erau scrise toate prefixele numărului a, inclusiv numărul a. Pe al treilea rând era scrisă regula: cifrul pentru deschiderea sipetului este format din suma a două numere, pe care le notăm x şi y. Numărul x este egal cu numărul de numere din şirul prefixelor care se divid cu numărul de cifre ale numărului a. Numărul y este egal cu numărul de numere din şirul de diferenţe a oricăror două numere din şirul prefixelor (prefixe ce nu sunt divizibile cu numărul de cifre ale numărului dat), cu proprietatea că se divid la numărul de cifre ale numărului iniţial. Ajutaţi-l pe bunicul Gepetto să găsească cifrul.
Cerinţă
Scrieţi un program care determină cifrul de deschidere al sipetului, pornind de la algoritmul găsit de bunicul Gepetto în carneţel.
Date de intrare
Fişierul de intrare cifru4.in conţine pe prima linie numărul natural a.
Date de ieşire
Fişierul de ieşire cifru4.out va conţine o singură linie pe care se va afişa un număr natural k ce reprezintă cifrul de deschidere al sipetului.
Restricţii
• 0 < a ≤ 999999999
Exemple
cifru4.in
cifru4.out
Explicaţii
5429
2
Şirul prefixelor numărului a este:5;54;542;5429.Numărul cifrelor numărului a este 4. Nici un număr din şirul prefixelor nu este divizibil cu 4 ,deci x=0. Numărul numerelor rezultate ca diferenţă a oricăror două numere din şirul prefixelor şi divizibile cu 4 este 2,deci y=2.Cifrul este k=0+2=2
904859464
6
În şirul prefixelor există 3 numere divizibile cu numărul cifrelor numărului dat. În şirul diferenţelor oricăror două numere din şirul prefixelor există 3 numere divizibile cu 9.Deci cifrul este k=6.
6904
2
Şirul prefixelor este:6;69;690;6904. Numărul de cifre ale numărului dat este 4. În şir există un singur număr divizibil cu 4. Acesta este 6904. În şirul numerelor construite ca diferenţă a oricăror două numere se află numărul 684, divizibil cu 4. Deci cifrul este k=2.