#include #define F first #define S second #define MP make_pair #define pb push_back #define all(a) a.begin(), a.end() #define rall(a) a.rbegin(), a.rend() #define LCM(a, b) (a) / __gcd((a), (b)) * (b) #define CEIL(a, b) (a)/(b)+(((a)%(b))?1:0) #define log_2(a) (log((a)) / log(2)) #define ln '\n' using namespace std; using LL = long long; using ldouble = long double; using P = pair; using LP = pair; static const int INF = INT_MAX; static const LL LINF = LLONG_MAX; static const int MIN = INT_MIN; static const LL LMIN = LLONG_MIN; static const int MOD = 1e9 + 7; static const int SIZE = 200005; const int dx[] = {0, -1, 1, 0}; const int dy[] = {-1, 0, 0, 1}; vector Div(LL n) { vector ret; for(LL i = 1; i * i <= n; ++i) { if(n % i == 0) { ret.pb(i); if(i * i != n) ret.pb(n / i); } } sort(all(ret)); return ret; } int main() { ios::sync_with_stdio(false); cin.tie(0); string s; cin >> s; int res = ((s[0] - '0') * 10 + s[1] - '0') / 3; if(s.size() <= 2) { cout << res - 3 << endl; return 0; } int tmp = 0; int dp[10][10][2] = {}; for(int i = 0; i < s.size() - 2; ++i) { int c = s[i] - '0'; if(i == 0) { if(c % 3 == 0) { dp[0][c][1] = 1; } for(int j = 0; j < c; ++j) { if(j % 3 == 0) dp[0][j][0] = 1; } } else { if(c % 3 == 0) { for(int j = 0; j <= 9; ++j) { dp[i][c][1] += dp[i - 1][j][1]; } } for(int j = 0; j <= 9; ++j) { if(j % 3 != 0) continue; for(int k = 0; k <= 9; ++k) { dp[i][j][0] += dp[i - 1][k][0]; } for(int k = 0; k < c; ++k) { dp[i][j][0] += dp[i - 1][k][1]; } } } } for(int i = 0; i <= 9; ++i) { tmp += dp[int(s.size()) - 2 - 1][i][0]; } tmp--; int cnt = 4; int ccnt = 0; for(int i = 10; i < 100; ++i) { int t = i; bool f = true; while(t > 0) { if(t % 10 % 3 != 0) { f = false; break; } t /= 10; } if(f) ++cnt; if(i % 3 == 0) ++ccnt; } res = tmp * cnt + ccnt; bool flg = false; for(int i = 0; i <= 9; ++i) { flg = (flg || dp[int(s.size()) - 2 - 1][i][1] != 0); } if(flg && (s[s.size() - 2] - '0') % 3 == 0 && (s[s.size() - 1] - '0') % 3 == 0) { tmp = (s[s.size() - 2] - '0') * 10 + s[s.size() - 1] - '0'; for(int i = 0; i <= tmp; i += 3) { if(i <= 9) ++res; else { if(i % 10 % 3 == 0 && i / 10 % 3 == 0) ++res; } } } cout << res << endl; return 0; }