조지 루카스와 1138

《스타워즈》의 감독 조지 루카스가 숫자 1138에 유난히 집착했다는 것은 잘 알려진 사실이다. 그의 첫 영화 제목이 《THX 1138》이었고, 그는 여러 작품을 하나로 잇기 위해 특정 단어와 숫자를 반복해서 쓰기를 즐겼다. 《에피소드 V》에서는 죄수가 1138호 감방에서 이송되고, 《에피소드 II》에서는 모든 클론 트루퍼가 헬멧 뒤에 1138을 큼지막하게 달고 있으며, 《에피소드 III》 DVD를 보다가 1138을 입력하면 요다가 브레이크 댄스를 추는 장면으로 곧장 넘어간다.

덜 알려진 이야기로, 출판되지 않은 《에피소드 제로: 죽음의 클레이니 스타의 탄생》이 있다. 고향 행성 타투인의 학교에 다니는 어린 드로이드 C3PO는 숫자 1, 1, 3, 8을 +, -, *, / 연산자와 괄호로 결합해 양수를 만드는 모든 방법을 찾으라는 과제를 받는다. C3PO는 곧바로 8 / 3 / 1 - 1이 1을, 3 / 8 + 1 + 1이 2를, ( 8 / 3 + 1 ) * 1이 3을 만든다는 것을 알아챈다. 그리고 몇 초 만에, 만들 수 없는 가장 작은 양의 정수가 29라고 단언한다. 과연 그의 말이 맞을까?

길이가 $n$인 숫자 문자열($1 \le n \le 7$)이 주어질 때, 그 $n$개의 숫자를 +, -, *, /와 괄호로 결합해 얻을 수 있는 모든 값을 고려하여, 만들 수 없는 가장 작은 양의 정수를 출력하라.

예를 들어 문자열 12345로는 1부터 75까지 모두 만들 수 있지만 76은 만들 수 없고, 13555로는 1부터 55까지 만들 수 있지만 56은 만들 수 없다.

규칙

• 중복을 포함해 모든 숫자를 반드시 사용해야 한다.
• 숫자를 이어 붙이는 것(연접)은 허용되지 않는다. 즉 12345에서 12 + 345 같은 항은 만들 수 없다.
• 나눗셈은 0 방향으로 버림하는 정수 나눗셈으로, C/Java의 long 나눗셈과 정확히 같다. 따라서 4 * ( 5 / 4 )는 5가 아니라 4이다(물론 ( 4 * 5 ) / 4는 5이다).
• 0으로 나누는 연산은 금지되며, 어떤 값도 만들어 내지 않는다.
• 모든 중간 결과와 최종 결과가 부호 있는 32비트 정수 범위에 들어가도록 입력이 보장된다.

여러 개의 숫자 문자열이 한 줄에 하나씩 주어진다. 0 하나만 있는 줄은 입력의 끝을 의미하며, 이 줄은 처리하지 않는다.

각 입력 줄마다 한 줄씩, 모든 숫자를 사용하는 어떤 산술식으로도 만들 수 없는 가장 작은 양의 정수를 출력하라.