디스크 문제

특수 문자열 저장소(SSS)에는 거대한 문자열 뱅크가 있다. 각 문자열마다 순환 중복 검사 코드(CRC)도 함께 저장된다. SSS의 하드 디스크는 매우 안정적이어서 각 문자열은 최대 한 비트만 손상될 수 있다.

Byteazar는 이런 오류를 복구하는 프로그램을 작성해야 한다. 그러기 위해서는 다음 문제를 풀어야 한다.

체 $GF(2)$ 위의 일변수 다항식을 생각하자. 계수는 $0$과 $1$만 가능하고, 모든 계산은 모듈로 $2$로 수행된다. $P(x) = x^{32} + x^{26} + x^{15} + x^7 + 1$이라 하자. 다항식 $P(x)$는 놀라운 성질이 있다. $0 \le i, j < 2^{32}$인 서로 다른 두 정수 $i$와 $j$에 대해, 다항식 $x^i \bmod P(x)$와 $x^j \bmod P(x)$도 서로 다르다.

여기서 $A(x) \bmod B(x)$는 다항식 $A(x)$를 $B(x)$로 나눈 나머지이다. 형식적으로 $A(x) \bmod B(x) = R(x)$이고, $R(x)$에서 $x$의 최고 차수는 $B(x)$에서 $x$의 최고 차수보다 작으며, $A(x) = Q(x) \times B(x) + R(x)$인 다항식 $Q(x)$가 존재한다. 정수 나눗셈과 마찬가지로, 임의의 다항식 $A(x)$와 영이 아닌 다항식 $B(x)$에 대해 이런 $Q(x)$와 $R(x)$는 각각 정확히 하나씩 존재한다. 예를 들어 $x^{32} \bmod P(x) = x^{26} + x^{15} + x^7 + 1$이고, 이때 $Q(x) = 1$이다.

주어진 각 다항식 $Q(x)$에 대해, Byteazar는 $x^k \bmod P(x)$가 $Q(x)$와 같아지는 최소의 음이 아닌 정수 $k$를 찾아야 한다. 그를 도와주자.

입력은 하나 이상의 테스트 케이스로 이루어진다.

각 테스트 케이스는 다항식 $Q(x)$를 포함하는 한 줄로 이루어진다. 각 다항식은 하나 이상의 항으로 이루어지며, 연속한 항은 문자 '+'로 구분된다. 각 항은 x^k 형태로 주어지고, 여기서 차수 $k$는 $0 \le k < 32$인 정수이다. 모든 항은 서로 다르고 $k$가 감소하는 순서로 주어진다. 입력에는 공백이 없다.

테스트 케이스는 최대 $200$개이다. 입력은 하나의 0만 포함하는 줄로 끝나며, 이 줄은 테스트 케이스로 취급하지 않는다.

각 테스트 케이스에 대해 문제의 답을 한 줄에 출력한다.