use strict;

sub pass_divcheck { # dups and 0s are assumed already handled
  my ($test_number) = @_;
  for ( split(//,$test_number) ) {
    return 0 unless $test_number % $_ == 0 ;
  }
  return 1;
}

sub form_number {
  my ($num, @remaining_digits) = @_;
  print "$num\n" if pass_divcheck($num);

  # When dealing with the three low-order digits, we can eliminate some
  # possibilities.  E.g. Any number divisible by 4 must end in a 2-digit
  # number divisible by 4.
  my $ndig = length($num);
  if ($ndig == 1) {
    if ($num % 2 != 0) {
      @remaining_digits = grep($_ % 2, @remaining_digits);
    }
    # After we have one digit, either 5 is already used or we
    # can't use 5 later anyway
    @remaining_digits = grep($_ % 5, @remaining_digits);
  } elsif ($ndig == 2) {
    if ($num % 4 != 0) {
      @remaining_digits = grep($_ % 4, @remaining_digits);
      return if ($num =~ /[48]/);
    }
  } elsif ($ndig == 3) {
    if ($num % 8 != 0) {
      @remaining_digits = grep($_ % 8, @remaining_digits);
    }
  }
  my $maxp = $#remaining_digits;
  foreach my $p (0..$maxp) {
    form_number($remaining_digits[$p] . $num,
                @remaining_digits[0..$p-1], @remaining_digits[$p+1..$maxp]);
  }
}

form_number('', (1..9));