Problem Description
Counting strings has been an interesting thing for Mr. Frog since he was 6 years old. Whenever given a string s, Mr. Frog may tell you how many strings in the same length are lexicographically smaller than or equal to s. But now, as an university student, elementary questions may not arouse Mr. Frog’s interest, so a harder question appeared.
We call a string t representative string if t is the lexicographically smallest string in an equivalence class of strings under rotation. Given s, Mr. Frog wants to know how many representative strings t, in the same length as s, are lexicographically smaller than or equal to s. In order to be a magician, you may want to solve this challenge quickly to attract Mr. Frog’s attention.
Only those t consisting of lowercase letters should be considered.
Input
The first line contains only one integer T(T≤30), which indicates the number of test cases.
For each test case, there is only one line describing the given string s(1≤|s|≤100), s consists of lowercase letters.
Output
For each test case, output one line “Case #x: y”, where x is the case number (starting from 1) and y is the number of representative strings to this question modulo 1000000007
Sample Input
2
bb
bab
Sample Output
Case #1: 27
Case #2: 651
