CF1316B String Modification

Vasya has a string $ s $ of length $ n $ . He decides to make the following modification to the string: 1. Pick an integer $ k $ , ( $ 1 \leq k \leq n $ ). 2. For $ i $ from $ 1 $ to $ n-k+1 $ , reverse the substring $ s[i:i+k-1] $ of $ s $ . For example, if string $ s $ is qwer and $ k = 2 $ , below is the series of transformations the string goes through: - qwer (original string) - wqer (after reversing the first substring of length $ 2 $ ) - weqr (after reversing the second substring of length $ 2 $ ) - werq (after reversing the last substring of length $ 2 $ ) Hence, the resulting string after modifying $ s $ with $ k = 2 $ is werq. Vasya wants to choose a $ k $ such that the string obtained after the above-mentioned modification is lexicographically smallest possible among all choices of $ k $ . Among all such $ k $ , he wants to choose the smallest one. Since he is busy attending Felicity 2020, he asks for your help. A string $ a $ is lexicographically smaller than a string $ b $ if and only if one of the following holds: - $ a $ is a prefix of $ b $ , but $ a \ne b $ ; - in the first position where $ a $ and $ b $ differ, the string $ a $ has a letter that appears earlier in the alphabet than the corresponding letter in $ b $ .

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 5000 $ ). The description of the test cases follows. The first line of each test case contains a single integer $ n $ ( $ 1 \le n \le 5000 $ ) — the length of the string $ s $ . The second line of each test case contains the string $ s $ of $ n $ lowercase latin letters. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 5000 $ .

For each testcase output two lines: In the first line output the lexicographically smallest string $ s' $ achievable after the above-mentioned modification. In the second line output the appropriate value of $ k $ ( $ 1 \leq k \leq n $ ) that you chose for performing the modification. If there are multiple values of $ k $ that give the lexicographically smallest string, output the smallest value of $ k $ among them.

In the first testcase of the first sample, the string modification results for the sample abab are as follows : - for $ k = 1 $ : abab - for $ k = 2 $ : baba - for $ k = 3 $ : abab - for $ k = 4 $ : babaThe lexicographically smallest string achievable through modification is abab for $ k = 1 $ and $ 3 $ . Smallest value of $ k $ needed to achieve is hence $ 1 $ .