该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Background

Special for beginners, ^_^

Description

徐老师需要压缩学生的作业文本以节省存储空间。压缩规则为：将连续相同的字符用"字符+出现次数"的格式表示。例如字符串"aaabb"压缩后为"a3b2"。

但如果压缩后的字符串长度不小于原字符串长度，则保留原字符串不进行压缩。

Format

Input

第一行一个正整数$T(1 \leq T \leq 10)$，表示测试组数。

接下来$T$行，每行一个仅包含小写字母的字符串$s(1 \leq |s| \leq 10^5)$。

Output

对于每组测试，输出一行，表示压缩后的字符串（或原串）。

Samples

3
aaabb
abc
aabbcc

a3b2
abc
aabbcc

Limitation

1s, 1024KiB for each test case.