AT_abc409_d [ABC409D] String Rotation

You are given a string $ S=S_1S_2\dots S_N $ of length $ N $ consisting of lowercase English letters. You will perform the following operation on $ S $ exactly once: - Choose a contiguous substring of $ S $ with length at least $ 1 $ and cyclically shift it to the left by $ 1 $ . That is, choose integers $ 1 \leq \ell \leq r \leq N $ , insert $ S_\ell $ to the right of the $ r $ -th character of $ S $ , and then delete the $ \ell $ -th character of $ S $ . Find the lexicographically smallest string among all possible strings that $ S $ can become after the operation. You are given $ T $ test cases, so solve each of them.

The input is given from Standard Input in the following format: > $ T $ $ \mathrm{case}_1 $ $ \mathrm{case}_2 $ $ \vdots $ $ \mathrm{case}_T $ Each test case $ \mathrm{case}_i\;(1 \leq i \leq T) $ is given in the following format: > $ N $ $ S $

Output $ T $ lines. The $ i $ -th $ (1 \leq i \leq T) $ line should contain the answer for $ \mathrm{case}_i $ .

### Sample Explanation 1 - In the first test case, cyclically shifting from the $ 2 $ nd to the $ 7 $ th character gives `acodert`, which is lexicographically smallest. - In the second test case, no matter how you operate, you get `x`. - In the third test case, cyclically shifting from the $ 1 $ st to the $ 2 $ nd character gives `nsuke`, which is lexicographically smallest. ### Constraints - $ 1 \leq T \leq 10^5 $ - $ 1 \leq N \leq 10^5 $ - $ S $ is a string of length $ N $ consisting of lowercase English letters. - $ T $ and $ N $ are integers. - The sum of $ N $ over all test cases in a single input file is at most $ 10^5 $ .