比尔正在试图用折叠重复子序列的方式紧凑的表示由大写字母’A’到’Z’组成的字符序列。
例如,表示序列AAAAAAAAAABABABCCD的一种方式是10(A)2(BA)B2(C)D。
他通过以下方式定义了折叠的字符序列以及它们的展开变换:
1、包含带个字符的序列被认为是折叠序列,展开它得到的序列为它本身。
2、如果S和Q是两个折叠序列,并且S可以展开得到S’,Q可以展开得到Q’,则认为SQ也是一个折叠序列,并且SQ展开得到S’Q’。
3、如果S是折叠序列,则X(S)也是折叠序列,其中X为大于1的整数。如果S展开得到S’,则X(S)展开得到X个S’。
根据定义可以展开任意给出的折叠序列,现在给出原序列,请你将它折叠,并使得折叠序列包含尽可能少的字符数。