#!/usr/bin/perl -w

use strict;

my %seen;
my $limit = shift or die;
my $count = 0;
my $num = 1;
my $cache_limit = 9**2*log($limit)/log(10);

$|++;
while ($num <= $limit) {
  $count += &chain($num) == 89;
  $num++;
  #print "$num\r" if $num % 1000 == 0;
}
print "\n\n$count\n";

sub chain {
  my $start = shift;
  my $num = $start;

  my @chain;
  push @chain, $num;
  while (1) {

    my $s = 0;
    $s += $_**2 for split "", $num;
    $num = $s;
    push @chain, $num;

    return $seen{$num} if $start > $cache_limit;
    last if $seen{$num} or $num == 1 or $num == 89;
  }
  if ($seen{$num}) { $num = $seen{$num} };

  foreach (@chain) {
    next if $_ > $cache_limit or $seen{$_};
    $seen{$_} = $num;
  }
  #print "$start => ", ($seen{$num}||$num), "\n";

  return $seen{$num} || $num;
}