Smallest Lexicographical Rotation

Given a string s, find its lexicographically smallest rotation. A rotation is obtained by taking a suffix of the string and appending the prefix to its end. Formally, for a string s of length n, there are n rotations defined as $$R_i = s[i:] + s[:i]$$ for \(0 \le i < n\). Your task is to determine the smallest rotation in lexicographical order.

Example: For s = "cba", the rotations are "cba", "bac", and "acb". The lexicographically smallest rotation is "acb".

inputFormat

The first line contains an integer T, indicating the number of test cases. Each test case consists of a single line containing a non-empty string s.

outputFormat

For each test case, output the lexicographically smallest rotation of the string s on a new line.

1
cba

acb