Optimal Rest

Time Limit : 8 sec, Memory Limit : 65536 KB

Problem E: Optimal Rest

Music Macro Language (MML) is a language for textual representation of musical scores. Although there are various dialects of MML, all of them provide a set of commands to describe scores, such as commands for notes, rests, octaves, volumes, and so forth.

In this problem, we focus on rests, i.e. intervals of silence. Each rest command consists of a command specifier eRf followed by a duration specifier. Each duration specifier is basically one of the following numbers: e1f, e2f, e4f, e8f, e16f, e32f, and e64f, where e1f denotes a whole (1), e2f a half (1/2), e4f a quarter (1/4), e8f an eighth (1/8), and so on. This number is called the base duration, and optionally followed by one or more dots. The first dot adds the duration by the half of the base duration. For example, e4.f denotes the duration of e4f (a quarter) plus e8f (an eighth, i.e. the half of a quarter), or simply 1.5 times as long as e4f. In other words, eR4.f is equivalent to eR4R8f. In case with two or more dots, each extra dot extends the duration by the half of the previous one. Thus e4..f denotes the duration of e4f plus e8f plus e16f, e4...f denotes the duration of e4f plus e8f plus e16f plus e32f, and so on. The duration extended by dots cannot be shorter than e64f. For exapmle, neither e64.f nor e16...f will be accepted since both of the last dots indicate the half of e64f (i.e. the duration of 1/128).

In this problem, you are required to write a program that finds the shortest expressions equivalent to given sequences of rest commands.


The input consists of multiple datasets. The first line of the input contains the number of datasets N. Then, N datasets follow, each containing a sequence of valid rest commands in one line. You may assume that no sequence contains more than 100,000 characters.


For each dataset, your program should output the shortest expression in one line. If there are multiple expressions of the shortest length, output the lexicographically smallest one.

Sample Input


Output for the Sample Input


Source: ACM International Collegiate Programming Contest , ACM-ICPC Japan Alumni Group Practice Contest 2008, 2008-10-19