진법 알아내기

6과 9를 곱하면 몇이 될까? 정답은 42이다. 54로 생각했다면, 잠시 쉬었다가 문제를 푸는 것을 권장한다. 그 이유는 42는 13진법으로 계산했을 때 결과이기 때문이다.

2보다 크거나 같은 정수 B에 대해서, B진법의 모든 자리수는 0보다 크거나 같고, B-1보다 작거나 같은 정수이다. B진법 수를 읽으려면 가장 오른쪽 자리에 1을 곱하고, 두 번째 오른쪽 자리에 B를 곱하고, 세 번째 오른쪽 자리에 B2를 곱하고, ... 이와 같은 식으로 계속 곱해야 한다.

일부 등식은 어떤 진법을 사용했냐에 따라서 참과 거짓이 결정된다. 예를 들어, 2+2=4의 경우에 B≥5이면 항상 참이다. 4진법에는 4를 자리로 사용할 수 없기 때문에 B≥5이다. 하지만, 2+2=5와 같은 등식은 어떤 진법을 사용해도 참이 될 수 없다.

등식이 주어졌을 때, 어떤 진법을 사용하면 참이 되는지 구하는 프로그램을 작성하시오.

입력의 각 줄은 테스트 케이스 하나를 나타내며, 각 테스트 케이스는 "EXPR=EXPR"과 같은 형태이다. EXPR는 17자리를 넘지 않는 수식이다.

모든 수식은 항상 올바르며, '+', '*'와 '0'-'9'까지 숫자로 이루어져 있다. 수식이 '+'기호로 시작하는 경우는 없으며, 수의 앞에 불필요한 0이 붙어있는 경우도 없다.

입력의 마지막 줄에는 '='이 주어진다.

각 테스트 케이스마다 어떤 진법을 사용하면 입력으로 주어진 등식이 참이 되는지 출력한다.

등식을 참으로 만드는 진법이 무한대인 경우에는 "B+"를 출력한다. 여기서 B는 등식을 참으로 만드는 가장 작은 진법이다.

진법의 수가 유한개인 경우에는 진법을 오름차순으로 공백으로 구분하여 출력한다.

어떤 진법을 사용해도 등식이 참이 되지 않는 경우에는 '*'을 출력한다.