Se consideră un șir S de cifre nenule. O secvență a șirului S este o succesiune de cifre din S care apar pe poziții consecutive. Un număr n asociat unei secvențe din S este numărul în baza 10 care se formează cu toate cifrele din secvența respectivă, în ordinea în care apar în aceasta.

Un număr n se numește caraghios dacă este egal cu pătratul sumei cifrelor lui n.

Cerința

Dându-se un șir S de cifre nenule, să se determine câte dintre secvențele din S au numere asociate caraghioase.

Date de intrare

Fișierul de intrare caraghios.in conține pe prima linie șirul S de cifre nenule.

Date de ieșire

Fișierul de ieșire caraghios.out va conține pe prima linie numărul de secvențe din S care au asociate numere caraghioase.

Restricții și precizări

• Șirul S va conține maxim 1.000.000 de cifre

Exemplu

caraghios.in

28113

caraghios.out

3

Explicație

Toate secvențele lui S sunt: 2, 28, 281, 2811, 28113, 8, 81, 811, 8113, 1, 11, 113, 1, 13, 3
Există 3 secvențe care au asociate numere caraghioase: 81, 1, 1
81 = (8+1)*(8+1), 1 = 1*1, 1 = 1*1

#include <bits/stdc++.h>
using namespace std;
ifstream cin("caraghios.in");
ofstream cout("caraghios.out");
int main()
{
    long long cnt = 0;
    char x , y;
    cin >> x;
    if(x=='1') cnt++;
    y = x;
    while(cin >> x)
    {
        if(x=='1') cnt++;
        if(y=='8' && x=='1') cnt++;
        y = x;
    }
    cout << cnt;
    return 0;
}