#!/usr/bin/env perl

use strict;
use warnings;

use Data::Dumper;
use Time::HiRes qw(time);
my $time = time;
$ENV{'DEBUG'} = 0;

my $n = <STDIN>;
chomp $n;

my @a = split / /, scalar <STDIN>;
chomp @a;

my $runs = 0;
my $cache = {};
my $lpf_cache = {};
my $tests = 0;
my $result = longestSequence(@a);
warn time - $time;

print "$result\n";
print "out of $runs\n" if $ENV{'DEBUG'};

foreach my $key (sort { $a <=> $b } keys %$cache) {
    print "$key => $cache->{$key}\n" if $ENV{'DEBUG'};
}

print "largest prime factor\n" if $ENV{'DEBUG'};

foreach my $key (sort { $a <=> $b } keys %$lpf_cache) {
    print "$key => $lpf_cache->{$key}\n" if $ENV{'DEBUG'};
}

warn $tests if $ENV{'DEBUG'};

sub longestSequence {
    $runs++;
    my @sticks = @_;
    warn 'received ', @sticks if $ENV{'DEBUG'};

    my $sum = 0;
    $sum += $cache->{$_} ||= _longestSequence($_) foreach @sticks;

    warn 'total ', $sum if $ENV{'DEBUG'};
    return $sum;
}

sub _longestSequence {
    my $stick = shift;
    warn 'stick ', $stick if $ENV{'DEBUG'};

    return $stick if $stick <= 1;
    
    my @hist = ();
    while ($stick > 1) {
        my $lpf = $lpf_cache->{$stick} ||= simple_lpf($stick);
        $stick /= $lpf;
        my $prev = $hist[-1] || 1;
        push @hist, $prev * $lpf;
    }
    
    my $sum = 1;
    $sum += $_ foreach @hist;
    return $sum;
}

sub simple_lpf {
    my $number = shift;
        
    my $i = 0;
    my %sieve = ();
    for ($i = 2; $i <= $number; $i++) {
        #next if $sieve{$i};
        return $number if $i > sqrt($number);
        if ($number % $i == 0) {
        warn "matched on $i";
            $number /= $i;
            $i--;
        } else {
            #$sieve{$i * $_}++ foreach 1..int($number/2/$i);
        }
    }

    return $i;
}