유효한 진법 찾기

자리값 기수법에서 밑(base 또는 radix)은 그 체계에서 수를 나타내는 데 쓰는 기호의 개수다. 10진법은 0, 1, ..., 9라는 서로 다른 기호 10개를 쓴다. 예를 들어 72345는 다음과 같이 해석한다.

$7 \times 10^4 + 2 \times 10^3 + 3 \times 10^2 + 4 \times 10^1 + 5 \times 10^0$

10진법에서 오른쪽부터 센 $P \ge 0$번째 자리의 기호는 $10^P$을 곱해 값을 얻는다. 일반적으로 밑이 $B$인 체계는 $0$부터 $B-1$까지를 나타내는 기호 $B$개를 쓰고, $P$번째 자리의 기호에는 $B^P$를 곱한다.

계산에 자주 쓰는 다른 밑으로는 2진법(기호 0과 1), 8진법(기호 0부터 7), 16진법(기호 0부터 9와 a부터 f)이 있다. 밑이 10보다 큰 체계에서는 문자가 더 큰 값을 나타낸다. 16진법에서 a부터 f는 10진수 10부터 15를 뜻하고, 밑이 36인 체계에서 z는 10진수 35를 뜻한다.

주어진 산술식이 어느 밑에서 성립하는지 판정하라. 다음 두 조건을 모두 만족하면 그 식은 밑 $B$에서 유효하다.

• 식에 쓰인 피연산자를 모두 밑 $B$로 해석한 값이 10진수 범위 $[1, 2^{32} - 1]$ 안에 있다.
• 식이 참이다. 나눗셈 /는 나머지 없이 딱 나누어떨어질 때만 참이다.

어떤 식은 유효한 밑이 하나도 없을 수도 있고, 하나이거나 여럿일 수도 있다. 이 문제에서는 밑 1부터 36까지만 생각하며, 밑 1은 1진법이다.

위 규칙을 그대로 따르면 1진법은 기호 0 하나만 쓰게 된다. 이 문제의 1진법은 0 대신 1을 쓴다. 작대기를 하나씩 세는 방식이다. 1진법 111은 10진수 3이고, 1111111은 10진수 7이다.

첫 줄에 식의 개수 $N$ $(0 \le N \le 20)$이 주어진다. 이어지는 $N$개의 줄에는 각각 다음 형태의 산술식이 주어진다.

X op Y = Z

$X$, $Y$, $Z$는 0부터 9와 a부터 z 사이의 기호 1개 이상 100개 이하로 이루어진 양의 정수이고, op는 +, -, *, / 중 하나다. 각 식에는 $X$, $Y$, $Z$를 모두 밑 $B$로 해석한 값이 10진수 범위 $[1, 2^{32} - 1]$ 안에 들어가는 밑 $B$ $(1 \le B \le 36)$가 적어도 하나 있다.

각 식마다 그 식이 유효한 밑을 작은 것부터 차례로 이어 붙여 한 줄에 출력한다. 밑 1부터 36 어디에서도 유효하지 않으면 invalid를 출력한다. 밑 1부터 9는 기호 1부터 9로, 밑 10부터 35는 a부터 z로, 밑 36은 0으로 나타낸다.