Smallest Lexicographic Rotation

You are given a list of words. For each word, your task is to compute its lexicographically smallest rotation.

A rotation of a word w is obtained by moving a prefix of w to its end without changing the order of characters. For example, the rotations of "bca" are "bca", "cab", and "abc", where "abc" is the lexicographically smallest rotation.

Input/Output via standard input and output.

Note: A word w of length n has exactly n rotations. Formally, if w = w_1 w_2 \ldots w_n, then its rotations are given by \[ w_i w_{i+1} \ldots w_n w_1 \ldots w_{i-1} \] for \(1 \leq i \leq n\).

inputFormat

The first line of input contains an integer T (\(1 \le T \le 10^4\)) representing the number of words.

The following T lines each contain a word consisting of lowercase English letters. The length of each word is at least 1 and can be assumed to be reasonably small.

outputFormat

For each word, output a line containing its lexicographically smallest rotation.

3
bca
zxy
abc

abc
xyz
abc