#!/usr/bin/perl
use strict;
use bigint; # optionally with eg C< lib => 'Pari' >

my $max = shift || 10;
my @try;

# deal with '1' explicitly
my %seen = (1 => 's');
my $waiting = $max - 1;
print "1 => s\n";

insert(3, '');

while (@try) {
  my $n = shift @try;
  my $s = 'f' . $seen{$n};
  $n->bfac; # $n = ($n)!
  $s = "f$s";
  while (!defined $seen{$n}) { 
    insert($n, $s);
    $n = sqrt($n);
    $s = "s$s";
  } 
}

sub insert {
  my($n, $s) = @_;
  if ($n <= $max) { 
    print "$n => $s\n";
    exit 0 unless --$waiting;
  } 
  $seen{$n} = $s;
  my($min, $max) = (0, scalar @try);
  while ($min + 1 < $max) { 
    my $new = ($min + $max) >> 1;
    if ($try[$new] > $n) {
      $max = $new; 
    } else {
      $min = $new; 
    }
  } 
  ++$min if $min < @try && $try[$min] < $n;
  splice @try, $min, 0, $n;
}