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 "bits/stdc++.h"
#include<unordered_map>
#include<unordered_set>
#pragma warning(disable:4996)
using namespace std;
using ld = long double;
const ld eps = 1e-9;



/* 幾何の基本 */

#include <complex>

typedef complex<ld> Point;


const ld pi = acos(-1.0);
const ld dtop = pi / 180.;
const ld ptod = 1. / dtop;

namespace std {
	bool operator<(const Point &lhs, const Point &rhs) {
		if (lhs.real() < rhs.real() - eps) return true;
		if (lhs.real() > rhs.real() + eps) return false;
		return lhs.imag() < rhs.imag();
	}
}

// 点の入力
Point input_Point() {
	ld x, y;
	cin >> x >> y;
	return Point(x, y);
}

// 誤差つき等号判定
bool eq(const ld a, const ld b) {
	return (abs(a - b) < eps);
}

// 内積
ld dot(const Point& a, const Point& b) {
	return real(conj(a) * b);
}

// 外積
ld cross(const Point& a, const Point& b) {
	return imag(conj(a) * b);
}

// 直線の定義
class Line {
public:
	Point a, b;
	Line() : a(Point(0, 0)), b(Point(0, 0)) {}
	Line(Point a, Point b) : a(a), b(b) {}
	Point operator[](const int _num)const {
		if (_num == 0)return a;
		else if (_num == 1)return b;
		else {
			assert(false);
			return Point();
		}
	}
};

// 円の定義
class Circle {
public:
	Point p;
	ld r;
	Circle() : p(Point(0, 0)), r(0) {}
	Circle(Point p, ld r) : p(p), r(r) {}
};

// ccw
// 1: a,b,cが反時計周りの順に並ぶ
//-1: a,b,cが時計周りの順に並ぶ
// 2: c,a,bの順に直線に並ぶ
//-2: a,b,cの順に直線に並ぶ
// 0: a,c,bの順に直線に並ぶ
int ccw(const Point& a, const Point &b, const Point &c) {
	const Point nb(b - a);
	const Point nc(c - a);
	if (cross(nb, nc) > eps) return 1;   // a,b,cが反時計周りの順に並ぶ
	if (cross(nb, nc) < -eps) return -1; // a,b,cが時計周りの順に並ぶ
	if (dot(nb, nc) < 0) return 2;       // c,a,bの順に直線に並ぶ
	if (norm(nb) < norm(nc)) return -2;  // a,b,cの順に直線に並ぶ
	return 0;                          // a,c,bの順に直線に並ぶ
}


/* 交差判定 */

// 直線と直線の交差判定
bool isis_ll(const Line& l, const Line& m) {
	return !eq(cross(l.b - l.a, m.b - m.a), 0);
}

// 直線と線分の交差判定
bool isis_ls(const Line& l, const Line& s) {
	return isis_ll(l, s) &&
		(cross(l.b - l.a, s.a - l.a) * cross(l.b - l.a, s.b - l.a) < eps);
}

// 線分と線分の交差判定
bool isis_ss(const Line& s, const Line& t) {
	return ccw(s.a, s.b, t.a) * ccw(s.a, s.b, t.b) <= 0 &&
		ccw(t.a, t.b, s.a) * ccw(t.a, t.b, s.b) <= 0;
}

// 点の直線上判定
bool isis_lp(const Line& l, const Point& p) {
	return (abs(cross(l.b - p, l.a - p)) < eps);
}

// 点の線分上判定
bool isis_sp(const Line& s, const Point& p) {
	return (abs(s.a - p) + abs(s.b - p) - abs(s.b - s.a) < eps);
}

// 垂線の足
Point proj(const Line &l, const Point& p) {
	ld t = dot(p - l.a, l.b - l.a) / norm(l.a - l.b);
	return l.a + t * (l.b - l.a);
}

//線対象の位置にある点
Point reflect(const Line &l, const Point &p) {
	Point pr = proj(l, p);
	return pr * 2.l - p;
}

// 直線と直線の交点
Point is_ll(const Line &s, const Line& t) {
	Point sv = s.b - s.a, tv = t.b - t.a;
	assert(cross(sv, tv) != 0);
	return s.a + sv * cross(tv, t.a - s.a) / cross(tv, sv);
}
// 直線と直線の交点
vector<Point> is_ll2(const Line &s, const Line& t) {
	Point sv = s.b - s.a, tv = t.b - t.a;
	if (cross(sv, tv) != 0)return vector<Point>(1, is_ll(s, t));
	else {
		vector<Point>ans;
		for (int k = 0; k < 2; ++k) {
			if (isis_sp(s, t[k]) && find(ans.begin(), ans.end(), t[k]) == ans.end())ans.push_back(t[k]);
			if (isis_sp(t, s[k]) && find(ans.begin(), ans.end(), s[k]) == ans.end())ans.push_back(s[k]);
		}
		return ans;
	}
}
// 線分と線分の交点
//　重なってる部分あるとassert(false)
Point is_ss(const Line &s, const Line& t) {
	if (isis_ss(s, t)) {
		for (int k = 0; k < 2; ++k) {
			for (int l = 0; l < 2; ++l) {
				if (s[k] == t[l])return s[k];
			}
		}
		return is_ll(s, t);
	}
	else {
		//先にisis_ssしてね
		assert(false);
		return Point(0, 0);
	}
}
// 線分と線分の交点
vector<Point> is_ss2(const Line &s, const Line& t) {
	vector<Point> kouho(is_ll2(s, t));
	vector<Point>ans;
	for (auto p : kouho) {
		if (isis_sp(s, p) && isis_sp(t, p))ans.emplace_back(p);
	}
	return ans;
}
// 直線と点の距離
ld dist_lp(const Line& l, const Point& p) {
	return abs(p - proj(l, p));
}

//直線と直線の距離
ld dist_ll(const Line& l, const Line& m) {
	return isis_ll(l, m) ? 0 : dist_lp(l, m.a);
}

// 直線と線分の距離
ld dist_ls(const Line& l, const Line& s) {
	return isis_ls(l, s) ? 0 : min(dist_lp(l, s.a), dist_lp(l, s.b));
}

// 線分と点の距離
ld dist_sp(const Line& s, const Point& p) {
	Point r = proj(s, p);
	return isis_sp(s, r) ? abs(r - p) : min(abs(s.a - p), abs(s.b - p));
}

// 線分と線分の距離
ld dist_ss(const Line& s, const Line& t) {
	if (isis_ss(s, t)) return 0;
	return min({ dist_sp(s, t.a), dist_sp(s, t.b), dist_sp(t, s.a), dist_sp(t, s.b) });
}


//直線と直線の二等分線のベクトル
Line line_bisection(const Line &s, const Line &t) {
	const Point laglanju(is_ll(s, t));
	const Point avec = !(abs(laglanju - s[0])<eps) ? s[0] - laglanju : s[1] - laglanju;
	const Point bvec = !(abs(laglanju - t[0])<eps) ? t[0] - laglanju : t[1] - laglanju;

	return Line(laglanju, laglanju + (abs(bvec)*avec + abs(avec)*bvec) / (abs(avec) + abs(bvec)));
}
//点と点の垂直二等分線　aを左に見ながら
Line point_bisection(const Point&a, const Point&b) {
	const Point cen((a + b) / 2.l);
	const Point vec = (b - a)*Point(0, 1);
	return Line(cen, cen + vec);
}

//三つの点からなる外心
Point outer_center(const vector<Point>&ps) {
	assert(ps.size() == 3);
	Line l1 = point_bisection(ps[0], ps[1]);
	Line l2 = point_bisection(ps[1], ps[2]);
	return is_ll(l1, l2);
}


//三つの直線からなる内心
//三つの直線が並行でないことは確かめといてね
Point  inner_center(const vector<Line>&ls) {
	vector<Point>vertics;
	for (int i = 0; i <static_cast<int>(ls.size()); ++i) {
		vertics.push_back(is_ll(ls[i], ls[(i + 1) % 3]));
	}
	if (vertics[0] == vertics[1] || vertics[1] == vertics[2] || vertics[2] == vertics[0])return vertics[0];
	Line bi1(line_bisection(Line(vertics[0], vertics[1]), Line(vertics[0], vertics[2])));
	Line bi2(line_bisection(Line(vertics[1], vertics[2]), Line(vertics[1], vertics[0])));
	if (bi1[0] == bi2[0])return bi1[0];
	else {
		return is_ll(bi1, bi2);
	}
}

//三つの直線からなる傍心
//三つの直線が並行でないことは確かめといてね
vector<Point>  ex_center(const vector<Line>&ls) {
	vector<Point>vertics;
	for (int i = 0; i < static_cast<int>(ls.size()); ++i) {
		vertics.push_back(is_ll(ls[i], ls[(i + 1) % 3]));
	}
	if (abs(vertics[0] - vertics[1])<eps || abs(vertics[1] - vertics[2])<eps || (abs(vertics[2] - vertics[0])<eps))return vector<Point>();
	vector<Point>ecs;
	for (int i = 0; i < 3; ++i) {
		Line bi1(line_bisection(Line(vertics[i], vertics[i] * 2.0l - vertics[(i + 2) % 3]), Line(vertics[i], vertics[(i + 1) % 3])));
		Line bi2(line_bisection(Line(vertics[(i + 1) % 3], vertics[(i + 1) % 3] * 2.0l - vertics[(i + 2) % 3]), Line(vertics[(i + 1) % 3], vertics[i])));
		ecs.push_back(is_ll(bi1, bi2));
	}
	return ecs;
}


//a,b:並行
//c:並行でない
//三つの直線から同距離の位置を求める。
vector<Point>  same_dis(const vector<Line>&ls) {
	vector<Point>vertics;
	vertics.push_back(is_ll(ls[0], ls[2]));
	vertics.push_back(is_ll(ls[1], ls[2]));

	if (abs(vertics[0] - vertics[1]) < eps)return vector<Point>{vertics[0]};
	Line bis(line_bisection(ls[0], ls[1]));
	vector<Point>ecs;

	Line abi(line_bisection(Line(vertics[0], vertics[1]), ls[0]));
	ecs.push_back(is_ll(bis, abi));


	Line bbi(line_bisection(Line(vertics[0], 2.l*vertics[0] - vertics[1]), ls[0]));
	ecs.push_back(is_ll(bis, bbi));

	return ecs;
}
/* 円 */

// 円と円の交点
vector<Point> is_cc(const Circle& c1, const Circle& c2) {
	vector<Point> res;
	ld d = abs(c1.p - c2.p);
	ld rc = (d * d + c1.r * c1.r - c2.r * c2.r) / (2 * d);
	ld dfr = c1.r * c1.r - rc * rc;
	if (abs(dfr) < eps) dfr = 0.0;
	else if (dfr < 0.0) return res; // no intersection
	ld rs = sqrt(dfr);
	Point diff = (c2.p - c1.p) / d;
	res.push_back(c1.p + diff * Point(rc, rs));
	if (dfr != 0.0) res.push_back(c1.p + diff * Point(rc, -rs));
	return res;
}

/*
点が円の中にいるか
0 => out
1 => on
2 => in*/
int is_in_Circle(const  Point& p, const Circle &cir) {
	ld dis = abs(cir.p - p);
	if (dis > cir.r + eps)return 0;
	else if (dis < cir.r - eps)return 2;
	else return 1;
}
int is_in_Circle(const Circle &cir, const  Point& p) {
	ld dis = abs(cir.p - p);
	if (dis > cir.r + eps)return 0;
	else if (dis < cir.r - eps)return 2;
	else return 1;
}
/*
円lcが円rcの中にいるか
0 => out
1 => on
2 => in*/
int Circle_in_Circle(const Circle &lc, const  Circle&rc) {
	ld dis = abs(lc.p - rc.p);
	if (dis < rc.r - lc.r - eps)return 2;
	else if (dis>rc.r - lc.r + eps)return 0;
	else return 1;
}

// 円と直線の交点
vector<Point> is_lc(const Circle& c, const Line& l) {
	vector<Point> res;
	ld d = dist_lp(l, c.p);
	if (d < c.r + eps) {
		ld len = (d > c.r) ? 0.0 : sqrt(c.r * c.r - d * d); //safety;
		Point nor = (l.a - l.b) / abs(l.a - l.b);
		res.push_back(proj(l, c.p) + len * nor);
		res.push_back(proj(l, c.p) - len * nor);
	}
	return res;
}

// 円と線分の距離
vector<Point> is_sc(const Circle& c, const Line& l) {
	vector<Point> v = is_lc(c, l), res;
	for (Point p : v)
		if (isis_sp(l, p)) res.push_back(p);
	return res;
}

// 円と点の接線
vector<Line> tangent_cp(const Circle& c, const Point& p) {
	vector<Line> ret;
	Point v = c.p - p;
	ld d = abs(v);
	ld l = sqrt(norm(v) - c.r * c.r);
	if (isnan(l)) { return ret; }
	Point v1 = v * Point(l / d, c.r / d);
	Point v2 = v * Point(l / d, -c.r / d);
	ret.push_back(Line(p, p + v1));
	if (l < eps) return ret;
	ret.push_back(Line(p, p + v2));
	return ret;
}

// 円と円の接線
vector<Line> tangent_cc(const Circle& c1, const Circle& c2) {
	vector<Line> ret;
	if (abs(c1.p - c2.p) - (c1.r + c2.r) > -eps) {
		Point center = (c1.p * c2.r + c2.p * c1.r) / (c1.r + c2.r);
		ret = tangent_cp(c1, center);
	}
	if (abs(c1.r - c2.r) > eps) {
		Point out = (-c1.p * c2.r + c2.p * c1.r) / (c1.r - c2.r);
		vector<Line> nret = tangent_cp(c1, out);
		ret.insert(ret.end(), nret.begin(), nret.end());
	}
	else {
		Point v = c2.p - c1.p;
		v /= abs(v);
		Point q1 = c1.p + v * Point(0, 1) * c1.r;
		Point q2 = c1.p + v * Point(0, -1) * c1.r;
		ret.push_back(Line(q1, q1 + v));
		ret.push_back(Line(q2, q2 + v));
	}
	return ret;
}
//二つの円の重なり面積
ld two_Circle_area(const Circle&l, const Circle&r) {
	ld dis = abs(l.p - r.p);
	if (dis > l.r + r.r)return 0;
	else if (dis + r.r < l.r) {
		return r.r*r.r*pi;
	}
	else if (dis + l.r < r.r) {
		return l.r*l.r*pi;
	}
	else {
		ld ans = (l.r)*(l.r)*acos((dis*dis + l.r*l.r - r.r*r.r) / (2 * dis*l.r)) +
			(r.r)*(r.r)*acos((dis*dis + r.r*r.r - l.r*l.r) / (2 * dis*r.r)) -
			sqrt(4 * dis*dis*l.r*l.r - (dis*dis + l.r*l.r - r.r*r.r)*(dis*dis + l.r*l.r - r.r*r.r)) / 2;
		return ans;
	}

}

/* 多角形 */

typedef vector<Point> Polygon;



//多角形(複数の点)の最小包含円をO(N=頂点数)で求めるアルゴリズム
//同一直線上に三つの点がないこと
#include<random>
Circle welzl(vector<Point>ps) {
	struct solver {
		Circle solve(vector<Point>&ps, vector<Point>&rs) {
			if (ps.empty() || rs.size() == 3) {
				if (rs.size() == 1) {
					return Circle(Point(rs[0]), 0);
				}
				else if (rs.size() == 2) {
					return Circle((rs[0] + rs[1]) / 2.0l, abs(rs[1] - rs[0]) / 2);
				}
				else if (rs.size() == 3) {
					vector<Line> ls(3);
					for (int i = 0; i < 3; ++i) {
						ls[i] = Line(rs[i], rs[(i + 1) % 3]);
					}
					Point center = outer_center(rs);
					return Circle(center, abs(center - rs[0]));
				}
				else {
					return Circle(Point(), 0);
				}
			}
			else {

				Point p_ba = ps.back();
				ps.pop_back();
				Circle d = solve(ps, rs);
				ps.push_back(p_ba);
				if (is_in_Circle(d, p_ba)) {
					return d;
				}
				else {
					rs.push_back(p_ba);
					ps.pop_back();
					auto ans = solve(ps, rs);
					ps.push_back(p_ba);
					rs.pop_back();
					return ans;
				}
			}
		}
	}so;
	std::random_device rd;
	std::mt19937 mt(rd());
	shuffle(ps.begin(), ps.end(), mt);
	vector<Point>rs;
	Circle ans = so.solve(ps, rs);
	return ans;
}
// 面積
ld get_area(const Polygon &p) {
	ld res = 0;
	int n = p.size();
	for (int j = 0; j<n; ++j) res += cross(p[j], p[(j + 1) % n]);
	return res / 2;
}

//多角形の回転方向
bool is_counter_clockwise(const Polygon &poly) {
	ld angle = 0;
	int n = poly.size();
	for(int i=0;i<n;++i) {
		Point a = poly[i], b = poly[(i + 1) % n], c = poly[(i + 2) % n];
		angle += arg((c - b) / (b - a));
	}
	return angle > eps;
}

// 円の内外判定
/*0 => out
1 => on
2 => in*/
int is_in_Polygon(const Polygon &poly, const  Point& p) {
	ld angle = 0;
	int n = poly.size();
	for(int i=0;i<n;++i) {
		Point a = poly[i], b = poly[(i + 1) % n];
		if (isis_sp(Line(a, b), p)) return 1;
		angle += arg((b - p) / (a - p));
	}
	return eq(angle, 0) ? 0 : 2;
}
//円の内外判定2　高速
enum { out, on, in };
int convex_contains(const Polygon &P, const Point &p) {
	const int n = P.size();
	Point g = (P[0] + P[n / 3] + P[2 * n / 3]) / 3.0l; // inner-point
	int a = 0, b = n;
	while (a + 1 < b) { // invariant: c is in fan g-P[a]-P[b]
		int c = (a + b) / 2;
		if (cross(P[a] - g, P[c] - g) > 0) { // angle < 180 deg
			if (cross(P[a] - g, p - g) > 0 && cross(P[c] - g, p - g) < 0) b = c;
			else                                                  a = c;
		}
		else {
			if (cross(P[a] - g, p - g) < 0 && cross(P[c] - g, p - g) > 0) a = c;
			else                                                  b = c;
		}
	}
	b %= n;
	if (cross(P[a] - p, P[b] - p) < 0) return 0;
	if (cross(P[a] - p, P[b] - p) > 0) return 2;
	return 1;
}

// 凸包
//点や線を返すことも有り得るので注意
Polygon convex_hull(vector<Point> ps) {
	int n = ps.size();
	int k = 0;
	sort(ps.begin(), ps.end());
	Polygon ch(2 * n);
	for (int i = 0; i < n; ch[k++] = ps[i++])
		while (k >= 2 && ccw(ch[k - 2], ch[k - 1], ps[i]) <= 0) --k;
	for (int i = n - 2, t = k + 1; i >= 0; ch[k++] = ps[i--])
		while (k >= t && ccw(ch[k - 2], ch[k - 1], ps[i]) <= 0) --k;
	ch.resize(k - 1);
	return ch;
}



//凸カット
vector<Polygon> convex_cut(const Polygon &ps, const Line& l) {
	int n = ps.size();
	Polygon q;
	Polygon r;
	for(int i=0;i<n;++i) {
		Point a = ps[i], b = ps[(i + 1) % n];
		Line m = Line(a, b);
		if (ccw(l.a, l.b, a) != -1) q.push_back(a);
		if (ccw(l.a, l.b, a) != 1) r.push_back(a);
		if (ccw(l.a, l.b, a) * ccw(l.a, l.b, b) < 0 && isis_ll(l, m)) {
			q.push_back(is_ll(l, m));
			r.push_back(is_ll(l, m));
		}
	}
	const vector<Polygon>polys{ q,r };
	return polys;
}

Polygon cen(Polygon po) {
	Point cen;
	for (auto p : po) {
		cen += p;
	}
	cen /= po.size();
	for (auto&p : po) {
		p -= cen;
	}
	return po;
}

int get_id(string st,int& a) {
	assert(st[a]=='R');
	a++;
	int num=0;
	while (a != st.size() && st[a] != 'R'&&st[a]!='.') {
		num*=10;
		num+=st[a]-'0';
		a++;
	}
	num=64/num;
	int k=num;
	while (a != st.size() && st[a] != 'R') {
		assert(st[a]=='.');
		k/=2;
		num+=k;
		a++;
	}
	return num;
}

int get_num(string st) {
	int sum=0;
	int a=0;
	while (a != st.size()) {
		sum+=get_id(st,a);
	}
	return sum;
}

int main() {
	vector<string>dp(5000);
	dp[0]="";
	map<string,int>mp;
	for (int k = 1; k <= 64; k *= 2) {
		int num=64/k;
		string st="R"+to_string(k);
		mp[st]=num;
		for (int plus = k * 2; plus!=128; plus *= 2) {
			num+=64/plus;
			st+='.';
			mp[st]=num;
		}
	}
	for (int i = 0; i < 3000; ++i) {
		for (auto&& m : mp) {
			int j=i+m.second;
			string st=dp[i]+m.first;
			if (dp[j] == "" || (dp[j].size() > st.size()) || ((dp[j].size() == st.size() && dp[j] > st))) {
				dp[j] = st;
			}
		}
	}
	for (int i = 1000; i <= 2000; ++i) {
		int k=dp[i].find("R1.R1.");
		assert(k!=-1);
	}
	int N;cin>>N;
	while (N--){
		string st;cin>>st;
		int n=get_num(st);

		if (n < 3000) {
			cout<<dp[n]<<endl;
		}
		else {
			int x=n%384;
			int t=x+1920;

			int sa=n-t;
			int need=sa/384;

			int place=dp[t].find("R1.R1.R1.R1.");
			string ans=dp[t];
			string plus;
			for (int k = 0; k < need; ++k) {
				plus+="R1.R1.R1.R1.";
			}
			ans.insert(ans.begin()+place,plus.begin(),plus.end());
			cout<<ans<<endl;
		}
	}
	return 0;
}