Favorite Donut

Lulu has a sweet tooth. Her favorite food is ring donut. Everyday she buys a ring donut from the same bakery. A ring donut is consists of n parts. Every part has its own sugariness that can be expressed by a letter from a to z (from low to high), and a ring donut can be expressed by a string whose i-th character represents the sugariness of the i−th part in clockwise order. Note that z is the sweetest, and two parts are equally sweet if they have the same sugariness.

Once Lulu eats a part of the donut, she must continue to eat its uneaten adjacent part until all parts are eaten. Therefore, she has to eat either clockwise or counter-clockwise after her first bite, and there are 2n ways to eat the ring donut of n parts. For example, Lulu has 6 ways to eat a ring donut abc: abc,bca,cab,acb,bac,cba       . Lulu likes eating the sweetest part first, so she actually prefer the way of the greatest lexicographic order. If there are two or more lexicographic maxima, then she will prefer the way whose starting part has the minimum index in clockwise order. If two ways start at the same part, then she will prefer eating the donut in clockwise order. Please compute the way to eat the donut she likes most.

露露爱吃甜食。她最喜欢的食物是环形甜甜圈。每天她从同一个面包店买一个环形甜甜圈。环形甜甜圈由n个部分组成。每个部分具有其自身的糖度，甜度可以由从a到z（从低到高）的字母表示，并且环形甜甜圈可以以一个第i个字符 表示顺时针的第i个部分的糖度的字符串来表示。注意，z是最甜的，并且如果两个部分具有相同的糖度，则他们是一样甜的。

一旦露露吃了甜甜圈的一部分，她必须继续吃其未吃完的相邻部分，直到所有部分都吃完为止。因此，她在咬下后必须沿顺时针或逆时针吃完，所以有2n种方式吃有n个部分的环形甜甜圈。例如，露露有6种方式吃一个环形甜甜圈abc：abc，bca，cab，acb，bac，cba。露露喜欢吃最甜的部分，所以她实际上更喜欢以最大的字典序的方式。如果存在两个或更多个满足字典序最大的方式，则她将优选其起始部分下标最小的方式。如果两种方式从同一部分开始，则她将更喜欢以顺时针顺序食用甜甜圈。请计算吃最喜欢的甜甜圈的方式

First line contain one integer T,T≤20, which means the number of test case.

For each test case, the first line contains one integer n,n≤20000, which represents how many parts the ring donut has. The next line contains a string consisted of n lowercase alphabets representing the ring donut.

You should print one line for each test case, consisted of two integers, which represents the starting point (from 1 to n) and the direction (0 for clockwise and 1 for counterclockwise).

3
4
abab
4
aaab
10
abaababaab

2 0
4 0
2 1