codeforces1316B String Modification

Vasya has a string ss of length nn. He decides to make the following modification to the string:

1. Pick an integer kk, (1≤k≤n1≤k≤n).
2. For ii from 11 to n−k+1n−k+1, reverse the substring s[i:i+k−1]s[i:i+k−1] of ss. For example, if string ss is qwer and k=2k=2, below is the series of transformations the string goes through:
   • qwer (original string)
   • wqer (after reversing the first substring of length 22)
   • weqr (after reversing the second substring of length 22)
   • werq (after reversing the last substring of length 22)
   Hence, the resulting string after modifying ss with k=2k=2 is werq.

Vasya wants to choose a kk such that the string obtained after the above-mentioned modification is lexicographically smallest possible among all choices of kk. Among all such kk, he wants to choose the smallest one. Since he is busy attending Felicity 2020, he asks for your help.

A string aa is lexicographically smaller than a string bb if and only if one of the following holds:

• aa is a prefix of bb, but a≠ba≠b;
• in the first position where aa and bb differ, the string aa has a letter that appears earlier in the alphabet than the corresponding letter in bb.

Input

Each test contains multiple test cases.

The first line contains the number of test cases tt (1≤t≤50001≤t≤5000). The description of the test cases follows.

The first line of each test case contains a single integer nn (1≤n≤50001≤n≤5000) — the length of the string ss.

The second line of each test case contains the string ss of nn lowercase latin letters.

It is guaranteed that the sum of nn over all test cases does not exceed 50005000.

Output

For each testcase output two lines:

In the first line output the lexicographically smallest string s′s′ achievable after the above-mentioned modification.

In the second line output the appropriate value of kk (1≤k≤n1≤k≤n) that you chose for performing the modification. If there are multiple values of kk that give the lexicographically smallest string, output the smallest value of kk among them.

Example

Input

6
4
abab
6
qwerty
5
aaaaa
6
alaska
9
lfpbavjsm
1
p

Output

abab
1
ertyqw
3
aaaaa
1
aksala
6
avjsmbpfl
5
p
1

Note

In the first testcase of the first sample, the string modification results for the sample abab are as follows :

• for k=1k=1 : abab
• for k=2k=2 : baba
• for k=3k=3 : abab
• for k=4k=4 : baba

  The lexicographically smallest string achievable through modification is abab for k=1k=1 and 33. Smallest value of kk needed to achieve is hence 11.

思路 : 规律题，

/*qwerty k=1: qwerty| 

k=2: qwerty

     wqerty  1 2

     weqrty  2 3

     werqty  3 4

     wertqy  4 5

     werty|q 5 6   逆序

k=3: qwerty

     ewqrty  1 3

     erqwty  2 4

     ertwqy  3 5

     erty|qw 4 6   正序 

     

k=4: qwerty

     rewqty   1 4

     rtqwey   2 5

     rty|ewq  3 6   逆序 

k=5: qwerty

     trewqy    1 5

     ty|qwer   2 6  正序

k=6: qwerty

     y|trewq   1 6  逆序 

*/ 

当k = 2时，相当于把前面两位移到最后两位并翻转，后面的n-k位往前移，当k = 3时，相当于把前面两位移到最后两位但是不翻转，后面的n-k位往前移同理，只需要判断前k位往后移，移动后是否需要反转，并且将后n-k位往前移动就行了

//规律为当n-k%2等于0时前k位移动到最后并翻转

#include<bits/stdc++.h>
using namespace std;
string a,b,c;
int main()
{
	int t,n,k,i;
	cin>>t;
	while(t--)
	{
		cin>>n;
		cin>>a;
		b = a;
		int ans = 1;
		for(k = 1; k<=n; k++) {
			string s1=a.substr(0,k-1);   //substr为取字符串s中从0到k-2位的元素
			string s2=a.substr(k-1,n-k+1);
			if ((n - k)%2==0)	
			    reverse(s1.begin(),s1.end());  //reverse为翻转s1字符串
			c = s2+s1;
			if(b>c) {  //string可以直接比较大小
				b=c;
				ans=k;
			}
		}
		cout<<b<<endl;
		cout<<ans<<endl;
	} 
	return 0;
}