It is clearly a literal fact that a chain is only as strong as its weakest link. The conversion of that notion into a figurative phrase was established in the language in the 18th century. Thomas Reid’s Essays on the Intellectual Powers of Man (1786), included this line: In every chain of reasoning, the evidence of the last conclusion can be no greater than that of the weakest link of the chain, whatever may be the strength of the rest. In this problem a chain of length n is a string C = c1c2 . . . cn of n lowercase characters where cn is considered to be followed by c1 in a cyclical fashion. Character i is said to be weaker than character j in a chain C if the string cici+1 ...cnc1 ...ci−1 comes before the string cjcj+1 ...cnc1 ...cj−1 in lexicographical order. Given a chain C, your task is to find the weakest character in C. Input The first line of the input contains a non-negative integer N indicating the number of test cases. Each test case comprises a single line with a nonempty string C of at most 60 000 lowercase characters of the English alphabet ‘a’-‘z’. You may assume that a < b < · · · < z as usual. Output For each test case, output a line containing an integer w such that cw is the weakest character in the chain C. If there is more than one such value, then output the smallest one. Sample Input 4 ccpl abracadabra hocuspocus aa Sample Output 1 11 8 1