def count_perfect_three(N): s = str(N) n_len = len(s) if N < 10: return 0 # Count two-digit numbers where sum of digits is divisible by 3 and <= N two_digit_count = 0 for a in range(1, 10): for b in range(0, 10): num = a * 10 + b if num > N: continue if (a + b) % 3 == 0: two_digit_count += 1 # Count numbers with three or more digits where all digits are 0, 3, 6, 9 # Using digit DP allowed_digits = {'0', '3', '6', '9'} from functools import lru_cache @lru_cache(maxsize=None) def dfs(pos, tight, leading_zero, length): if pos == n_len: return 1 if length >= 3 else 0 limit = int(s[pos]) if tight else 9 total = 0 for d in range(0, limit + 1): new_tight = tight and (d == limit) new_leading_zero = leading_zero and (d == 0) new_length = length + 1 if not new_leading_zero else length # Check if the digit is allowed if str(d) not in allowed_digits: if not new_leading_zero: continue # invalid digit and already started forming the number elif d != 0: continue # leading_zero but digit is not 0 (since leading_zero can't have other digits) # Proceed to next position total += dfs(pos + 1, new_tight, new_leading_zero, new_length) return total three_or_more_count = dfs(0, True, True, 0) return two_digit_count + three_or_more_count N = int(input()) print(count_perfect_three(N))