UVa 719 - Glass Beads

// UVa 719 - Glass Beads

#include <stdio.h>
#include <string.h>

#define MAX_LENGTH 30000

char st[MAX_LENGTH * 2 + 1];

int main() {
	int cases;
	for (scanf("%d", &cases); cases; cases--) {
		scanf("%s", st);
		int n = strlen(st);
		for (int i = 0; i < n; i++)
			st[n + i] = st[i];
		st[n + n] = '\0';

		int lowest = 0;
		for (int candidate = 1; candidate < n; candidate++) {
			int cmp = strncmp(st + lowest, st + candidate, n);
			if (cmp > 0)
				lowest = candidate;
		}

		printf("%d\n", lowest + 1);
	}
	return 0;
}