Fumblemore 교수와 콜라츠 추측

양의 정수에 대한 콜라츠 함수 $C(n)$은 다음과 같다.

• $n$이 짝수이면 $C(n) = n/2$
• $n$이 홀수이면 $C(n) = 3n+1$

양의 정수 $n$의 콜라츠 수열 $CS(n)$은 $CS(n) = n, C(n), C(C(n)), C(C(C(n))), \ldots$ 이다.

예를 들어 $CS(12) = 12, 6, 3, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1, \ldots$ 이다.

콜라츠 추측(3n+1 문제라고도 한다)은 모든 양의 정수 $n$에 대해 $CS(n)$이 결국 4, 2, 1을 반복하며 끝난다는 추측이다. 이 추측의 참 여부는 아직 밝혀지지 않았다. 증명은 나오지 않았고, 매우 큰 값까지 반례도 발견되지 않았다.

Fumblemore 교수는 콜라츠 수열 유형을 이용해 이 문제를 연구하려 한다. 정수 $n$의 콜라츠 수열 유형 $CST(n)$은 $CS(n)$의 값들이 짝수인지 홀수인지를 E(짝수)와 O(홀수)로 나타낸 문자열이다. 단, 처음으로 나오는 2의 거듭제곱은 포함하지 않는다. 따라서

$CST(12) = EEOEO$

이다.

참고로

$CS(908) = 908, 454, 227, 682, 341, 1024, 512, 256, 128, 64, 32, 16, 8, 4, 3, 2, \ldots$

이므로 12와 908은 같은 CST를 가진다.

Fumblemore 교수에게는 E와 O로 이루어진 문자열을 입력받아, 그 문자열이 $CST(n)$이 되는 가장 작은 정수 $n$을 구하는 프로그램이 필요하다.

참고:

• E는 2의 거듭제곱이 아닌 짝수이다.
• O는 1보다 큰 홀수이다.
• 문자열의 마지막 글자는 반드시 O여야 한다($C(n)$이 2의 거듭제곱이면 $n$도 2의 거듭제곱이다).
• O가 연속으로 나올 수 없다. 홀수의 $C$ 값은 짝수이기 때문이다.
• Fumblemore 교수는 타자를 잘 치지 못하므로, $n$을 찾기 전에 입력이 유효한지 반드시 확인해야 한다. 즉 문자열은 E와 O만 포함하고, O로 끝나며, O가 인접하지 않아야 한다.

E와 O로 이루어진 문자열이 한 줄에 최대 50글자까지 주어진다.

입력 수열이 유효하지 않으면 INVALID를 한 줄에 출력한다. 그렇지 않으면 입력 수열이 $CST(n)$이 되는 가장 작은 정수 $n$을 한 줄에 출력한다. 입력은 $n \le 247$이 되도록 주어진다.