화성인의 DNA 공식

A는 화성인의 DNA 공식을 알아냈습니다.

A는 많은 양의 땅콩을 받는 대가로 이 정보를 B에게 넘기려 합니다. 두 사람은 그 공식의 유포를 막으려는 기관이 대화를 엿들을 수 있다고 의심하여, 인적이 드문 빵집에서 만나 물건을 교환하기로 했습니다.

공식이 매우 길기 때문에 A는 가능한 한 쉽게 전달할 수 있도록 다음 규칙으로 공식을 짧게 쓰려고 합니다.

공식은 영어 알파벳 소문자로 이루어진 문자열입니다. 어떤 문자열이 여러 번 반복되면, 반복되는 부분을 괄호로 묶고 반복 횟수를 뒤에 붙여 줄일 수 있습니다. 예를 들어 abcabcabc는 (abc)3, axyxyxyxyb는 a(xy)4b로 쓸 수 있습니다. 축약은 중첩될 수 있어 mnmndefmnmndef를 ((mn)2def)2로 쓸 수도 있습니다.

공식의 길이는 괄호와 숫자를 포함하여 적힌 모든 문자의 수입니다.

공식이 주어졌을 때, 새로 적은 공식의 길이가 최소가 되도록 축약한 결과를 출력하세요.

최적의 표현은 여러 개일 수 있습니다.

입력은 한 줄로 이루어지며 DNA 공식이 주어집니다. 공식의 길이는 최대 1000자입니다.

한 줄에 가장 짧게 쓴 공식을 출력합니다. 길이가 최소인 표현이 여러 개라면 그중 아무거나 출력해도 됩니다.