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