use strict;
use prime;

# p = a^2 + b^3 + c^4
# 
my $N = 50000000;
my $a_max = int($N ** (1 / 2));
my @prime = prime::make_prime_table(1000000);
my $count = 0;

my %ext;
for (my $a = 0; $prime[$a] <= $a_max; ++$a) {
  my $b_max = int(($N - $prime[$a] ** 2) ** (1 / 3));
  for (my $b = 0; $prime[$b] <= $b_max; ++$b) {
    my $c_max = int(($N - ($prime[$a] ** 2 + $prime[$b] ** 3)) ** (1 / 4));
    for (my $c = 0; $prime[$c] <= $c_max; ++$c) {
      my $p = $prime[$a] ** 2 + $prime[$b] ** 3 + $prime[$c] ** 4;
      if ($p < $N && !exists($ext{$p})) {
        #print "$prime[$a]^2 + $prime[$b]^3 + $prime[$c]^4\n";
        ++$count;
        ++$ext{$p};
      }
    }
  }
}
print "CNT=$count\n";