String Compression Using Repeating Patterns

Given a string s, compress it by representing it in the smallest possible k[x] format where k is the number of repetitions and x is the smallest repeating substring. If no such compression is possible, the original string should be returned.

For example, if s = "ababab", the smallest repeating unit is "ab" repeated 3 times, so the compressed form is "3[ab]". However, if the string does not consist of any repeating pattern (like "ababc"), then the output should be the string itself.

The task is to read multiple test cases from standard input and output each corresponding compressed result on a separate line.

inputFormat

The first line of input contains an integer T representing the number of test cases. This is followed by T lines, each containing a non-empty string that needs to be compressed.

Each string consists of lowercase letters only.

outputFormat

For each test case, output the compressed string on a separate line. If the string cannot be compressed into a k[x] format, output the string itself.

## sample

3
ababc
ababab
aabbaabbaabb

ababc
3[ab]
3[aabb]

</p>