Micro and Mini
Tag(s):

Algorithms, Easy-Medium, Hashing, String Algorithms, Suffix Arrays

Problem
Editorial
Analytics

Micro wanted to give a string as birthday gift to his girlfriend Mini, so he went to a string store. There were a lot of strings to choose from, but the strange thing was that there was no price tag on any string. So he asked the store keeper about this. He told Micro that to find out the price of any string just rotate it right N times, where N is the length of string (rotating right means converting the string from S[1], S[2], ... ,S[N-1], S[N] to S[N], S[1], S[2] ... ,S[N-1] , see sample explanation for more clarity) . While doing so one need to keep the count of distinct strings encountered. The value of count after rotating N times is the price of that string.
Micro asked for your help to find out the price of a given string.

Input:
The first line consists of a single integer T, the number of test cases.
Each of the next T lines consist of a string S. Each string is made up of lower case characters.

Output:
For each test case print the answer in a new line.

Constraints:
1 ≤ T ≤ 10
1 ≤ |S| ≤ 50000

SAMPLE INPUT
2
abcd
aaaaa

SAMPLE OUTPUT
4
1

Explanation

Rotating string "abcd" 4 times gives four strings: "dabc", "cdab", "bcda", "abcd". So the number of distinct strings is 4.
Rotating string "aaaaa" 5 times gives five strings: "aaaaa", "aaaaa", "aaaaa", "aaaaa", "aaaaa". Clearly number of distinct strings is 1.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Scala 2.11.8, Swift, Visual Basic

CODE EDITOR

Initializing Code Editor...