1. 

/**
* FWP, Ausgew√¤hlte Probleme aus dem ACM Programming Contest, SS10
* Problem: 719 - Glass Beads
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=9&problem=660&mosmsg=Submission+received+with+ID+8013402
*
* @author Evgeni Pavlidis
* @version 1.0, 06/02/2010
*
* Method : Duvals algorithm
* Status : Accepted
* Runtime: 0.220
*/

/* See: http://acm.uva.es/board/viewtopic.php?f=22&t=42601&p=100012&hilit=719&sid=03cd107abfff6031b7c93e118fcd07cb#p100012 */

import java.io.*;
import java.util.*;

public class Main {

public static void main (String[] args) throws Exception
{
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
Writer out = new BufferedWriter(new PrintWriter(System.out));
int testCases = Integer.parseInt(reader.readLine());

for (int tc = 0; tc < testCases; tc++)
{
String line = reader.readLine();

line += line;
int n = line.length();
char[] s = line.toCharArray();

int result = 0, k, j, i = 0;
while(i < n/2)
{
result = i;
k = i;

for(j = i+1; j < n && s[k] <= s[j]; j++)
if(s[k] < s[j])
k = i;
else
k++;

while(i <= k)
i += j - k;
}

out.write((result+1)+"\n");
}
out.close();
}
}


2.