use strict;
use warnings;

use Math::BigInt qw( );

# Skips over 0 and 1.
sub make_iter {
   my ($base) = @_;

   my $num = Math::BigInt->new(1);
   my @digits = 1;  # -1 represents zero.
   my @powers = Math::BigInt->new(1);

   return sub {
      if ($digits[-1] > 0) {
         push @digits, -1;
         push @powers, $powers[-1] * $base;
      }

      for (0..$#digits) {
         $digits[$_] = -$digits[$_];
         $num += $digits[$_] * $powers[$_];
         return $num if $digits[$_] > 0;
      }
   };
}

sub test {
   my ($num, $base) = @_;
   while ($num > 0) {
      my $digit = $num % $base;
      return 0 if $digit > 1;
      $num = ($num - $digit)/$base;
   }

   return 1;
}

{
   my $i = $ARGV[0] || 5;

   my $candidate_num;
   my $num;
   my $iter = make_iter($i);
CANDIDATE:
   while (1) {
      $num = $iter->();

      if (++$candidate_num == 10_000) {
         $candidate_num = 0;
         print("> $num\n");
      }

      for my $base (reverse 3..$i-1) {
         next CANDIDATE if !test($num, $base);
      }

      last;
   }

   print("$num\n");
}