유리 구슬

옛날에 온갖 종류의 구슬을 모으는 취미를 가진 유명한 여배우가 있었다. 많은 구슬 장인들이 매일 그녀를 위해 새로운 목걸이와 팔찌를 만들었다. 어느 날 그녀는 아주 길고 특별한 목걸이를 원한다고 말했다.

이 목걸이는 크기가 서로 다른 유리 구슬들을 실 없이 서로 이어 붙여 만든다. 그래서 목걸이는 이웃한 두 구슬 사이 어느 지점에서든 끊어질(분리될) 수 있다. 그런데 연결 부위가 약해서 목걸이가 자신의 무게로 끊어질 수 있고, 끊어지는 지점이 어디인지가 중요하다. 시작 부분에 작은 구슬이 있을수록 끊어질 가능성이 더 크다. 따라서 목걸이가 끊어질 수 있는 가장 나쁜(위험한) 지점을 찾아야 한다.

목걸이는 각 구슬의 크기를 나타내는 문자열 A = a_1 a_2 … a_m 으로 표현하며, 원형이므로 마지막 문자 a_m 다음에는 다시 첫 문자 a_1 이 이어진다.

분리 지점 i 가 분리 지점 j 보다 더 나쁘다는 것은, 문자열 a_i a_{i+1} … a_m a_1 … a_{i-1} 이 문자열 a_j a_{j+1} … a_m a_1 … a_{j-1} 보다 사전순으로 더 작다는 뜻이다. 문자열 x_1 x_2 … x_n 이 문자열 y_1 y_2 … y_n 보다 사전순으로 더 작다는 것은, 어떤 정수 k (1 ≤ k ≤ n) 가 존재하여 1 ≤ j < k 인 모든 j 에 대해 x_j = y_j 이고 x_k < y_k 인 경우를 말한다.

첫 줄에 테스트 케이스의 개수 N 이 주어진다. 이어서 N 개의 케이스가 주어지며, 각 케이스는 목걸이를 나타내는 문자열 하나로 이루어진 한 줄이다. 각 문자열의 길이는 최대 10000 이고, 각 구슬은 영어 소문자('a'부터 'z')로 표현된다. 여기서 'a' < 'b' < … < 'z' 이다.

각 케이스마다 한 줄에 정수 하나를 출력한다. 이 정수는 가장 나쁜 분리 지점에서 첫 번째로 오는 구슬의 번호 i 로, 목걸이를 끊어 만들 수 있는 n 가지 문자열 중 사전순으로 가장 작은 문자열을 만드는 i 이다. 그러한 i 가 여러 개라면 가장 작은 i 를 출력한다. 구슬 번호는 1부터 시작한다.