char s[5d5];ll@n,p;REP(n){rd(n,s);p=4d4;p+=2(s[p]==s[p+1]&s[p]>(s[--p]=s[n-(1..n)]));wt(s+p);}