Biến đổi xâu

Cho xâu $s$ độ dài $n$ gồm các chữ cái Latin in thường. Thực hiện phép biến đổi sau với một số nguyên $k$ ($1\le k\le n$):

Với $i$ chạy từ $1$ đến $n-k+1$, lần lượt đảo ngược đoạn con $s[i..i+k-1]$ của $s$.

Ví dụ, với $s=$ qwer và $k=2$, xâu biến đổi theo từng bước:

• qwer (ban đầu)
• wqer (đảo ngược đoạn $[1.\mathrm{.2}]$)
• weqr (đảo ngược đoạn $[2.\mathrm{.3}]$)
• werq (đảo ngược đoạn $[3.\mathrm{.4}]$)

Kết quả cuối cùng là werq.

Hãy tìm giá trị $k$ sao cho xâu thu được sau phép biến đổi có thứ tự từ điển nhỏ nhất. Nếu có nhiều $k$ cho cùng kết quả nhỏ nhất, xuất giá trị $k$ nhỏ nhất trong số đó.

Dữ liệu vào

Dòng đầu chứa số nguyên $t$ — số bộ test.

Mỗi bộ test gồm hai dòng:

• Dòng đầu chứa số nguyên $n$ — độ dài của xâu $s$.
• Dòng thứ hai chứa xâu $s$ độ dài $n$ gồm các chữ cái Latin in thường.

Dữ liệu ra

Với mỗi bộ test, in ra hai dòng:

• Dòng đầu: xâu có thứ tự từ điển nhỏ nhất có thể đạt được.
• Dòng thứ hai: giá trị $k$ nhỏ nhất tương ứng.

Ràng buộc

• $1\le t\le 5000$
• $1\le n\le 5000$
• Tổng $n$ trên tất cả bộ test không vượt quá $5000$.

Ví dụ