George Lucas and 1138

In Star Wars lore, director George Lucas was famously preoccupied with the number 1138. His first film was titled THX 1138, and he liked to reuse certain key words and numbers across his movies to tie all of his works together. In Episode V a prisoner is transferred from cell block 1138; in Episode II every clone trooper wears 1138 prominently on the back of the helmet; and typing 1138 while watching the Episode III DVD jumps straight to the scene where Yoda break-dances.

Less well known is the unpublished Episode Zero: The Birth of the Death Kleene Star. As a young droid attending school on his home planet of Tatooine, C3PO is asked to find every way the digits 1, 1, 3, and 8 can be combined with the operators +, -, *, / and parentheses to produce positive numbers. He quickly notices that 8 / 3 / 1 - 1 makes 1, 3 / 8 + 1 + 1 makes 2, and ( 8 / 3 + 1 ) * 1 makes 3. Within seconds he declares that the smallest positive integer that cannot be generated is 29. But is he right?

Given a digit string of length $n$ ($1 \le n \le 7$), consider every value obtainable by combining those $n$ digits with +, -, *, / and parentheses, and output the smallest positive integer that cannot be generated.

For the string 12345, every number from 1 to 75 can be generated, but 76 cannot. For 13555, every number from 1 to 55 can be generated, but 56 cannot.

Rules

• You must use all of the digits, including duplicates.
• Digits may not be joined by concatenation: for 12345, a term like 12 + 345 is not allowed.
• Division is integer division that truncates toward zero, exactly like C/Java long division. So 4 * ( 5 / 4 ) equals 4, not 5 (while ( 4 * 5 ) / 4 is of course 5).
• Division by zero is forbidden and never contributes a value.
• The test data guarantees that every intermediate and final result fits in a signed 32-bit integer.

The input is a series of digit strings, one per line. A line containing a single 0 marks the end of input and must not be processed.

For each input line, print one line: the smallest positive integer that cannot be produced by any arithmetic expression that uses all of the digits.