Problem: 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 ‘R’ followed by a duration specifier. Each duration specifier is basically one of the following numbers: ‘1’, ‘2’, ‘4’, ‘8’, ‘16’, ‘32’, and ‘64’, where ‘1’ denotes a whole (1), ‘2’ a half (1/2), ‘4’ a quarter (1/4), ‘8’ 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, ‘4.’ denotes the duration of ‘4’ (a quarter) plus ‘8’ (an eighth, i.e. the half of a quarter), or simply 1.5 times as long as ‘4’. In other words, ‘R4.’ is equivalent to ‘R4R8’. In case with two or more dots, each extra dot extends the duration by the half of the previous one. Thus ‘4..’ denotes the duration of ‘4’ plus ‘8’ plus ‘16’, ‘4...’ denotes the duration of ‘4’ plus ‘8’ plus ‘16’ plus ‘32’, and so on. The duration extended by dots cannot be shorter than ‘64’. For exapmle, neither ‘64.’ nor ‘16...’ will be accepted since both of the last dots indicate the half of ‘64’ (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.



Input

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.

Output

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.

Example

Input

3
R2R2
R1R2R4R8R16R32R64
R1R4R16


Output

R1
R1......
R16R1R4

Solution (in CPP):

Solution:
#include<iostream>
#include<algorithm>
#include<vector>
#include<algorithm>
using namespace std;
#define REP(i,b,n) for(int i=b;i<n;i++)
#define rep(i,n)   REP(i,0,n)
#define pb push_back
#define mp make_pair
#define ALL(C) (C).begin(),(C).end()
#define fi first
#define se second

typedef pair<int,string> pis;

const int    val[]={  64,  32,  16,  8,     4,    2,    1};
const string str[]={"R1","R2","R4","R8","R16","R32","R64"};

class st{
public:
  int sc;
  string s;
  bool operator<(const st & a)const{
    if (s.size() != a.s.size())return s.size() < a.s.size();
    return s < a.s;
  }
};

vector<st> all;
void make(){
  rep(i,7){
    int now =val[i];
    string snow=str[i];
    all.pb((st){now,snow});
    REP(j,i+1,7){
      now+=val[j];
      snow+=".";
      all.pb((st){now,snow});
    }
  }
  sort(ALL(all));
  //rep(i,all.size())printf("%4d %s\n",all[i].sc,all[i].s.c_str());
}

const int N = 6400010;
int dp[N];
int path[N];

int encode(string &in){
  int sum=0;
  int p=0;
  while(p < in.size()){
    p++;//in[p]='R';
    int now=0;
    while(p < in.size() && isdigit(in[p]))now=now*10+(in[p++]-'0');
    now = 64/now;
    sum+=now;
    while(p < in.size() && in[p] == '.')p++,sum+=now/2,now/=2;
  }
  return sum;
}

bool cmpstr(string &a,string &b){
  int len=min(a.size(),b.size());
  rep(i,len){
    if (a[i] != b[i])return a[i] < b[i];
  }
  return a.size() > b.size();
}

void solve(int tar){
  rep(i,tar+1)dp[i]=N*10,path[i]=-1;
  dp[0]=0;
  rep(i,tar+1){
    rep(j,all.size()){
      if (i-all[j].sc >= 0 && 
	  (all[j].s.size()+dp[i-all[j].sc] < dp[i] ||
	   (all[j].s.size()+dp[i-all[j].sc]==dp[i]&& 
	    cmpstr(all[j].s,all[path[i]].s)))){
	dp[i]=all[j].s.size()+dp[i-all[j].sc];
	path[i]=j;
      }
    }
  }
  while(path[tar] != -1){
    cout << all[path[tar]].s;
    tar=tar-all[path[tar]].sc;
  }
  cout << endl;
}

int main(){
  make();
  int te;
  cin>>te;
  while(te--){
    string in;
    cin>>in;
    solve(encode(in));
  }
  return false;
}