AT_abc409_d [ABC409D] String Rotation

長さ $ N $ の英小文字からなる文字列 $ S=S_1S_2\dots S_N $ が与えられます。あなたは、 $ S $ に対して以下の操作をちょうど $ 1 $ 回行います。 - $ S $ の長さ $ 1 $ 以上の連続部分文字列を選んで、左に $ 1 $ だけ巡回シフトする。すなわち、整数 $ 1 \leq \ell \leq r \leq N $ を選んで、 $ S $ の $ r $ 文字目の右に $ S_\ell $ を挿入したのち、 $ S $ の $ \ell $ 番目の文字を削除する。 操作後の $ S $ としてありえる文字列のうち、辞書順最小のものを求めてください。 $ T $ 個のテストケースが与えられるので、それぞれについて答えてください。

入力は以下の形式で標準入力から与えられる。 > $ T $ $ \mathrm{case}_1 $ $ \mathrm{case}_2 $ $ \vdots $ $ \mathrm{case}_T $ 各テストケース $ \mathrm{case}_i\;(1 \leq i \leq T) $ は以下の形式で与えられる。 > $ N $ $ S $

$ T $ 行出力せよ。 $ i \; (1 \leq i \leq T) $ 行目には、 $ \mathrm{case}_i $ に対する答えを出力せよ。

### Sample Explanation 1 - $ 1 $ 番目のテストケースでは、 $ 2 $ 文字目から $ 7 $ 文字目を巡回シフトして `acodert` とするのが辞書順最小です。 - $ 2 $ 番目のテストケースでは、どのように操作しても `x` が得られます。 - $ 3 $ 番目のテストケースでは、 $ 1 $ 文字目から $ 2 $ 文字目を巡回シフトして `nsuke` とするのが辞書順最小です。 ### Constraints - $ 1 \leq T \leq 10^5 $ - $ 1 \leq N \leq 10^5 $ - $ S $ は英小文字からなる長さ $ N $ の文字列 - $ T,N $ は整数 - $ 1 $ つの入力ファイルに含まれる $ N $ の総和は $ 10^5 $ 以下