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\leq 30)$, which indicates the number of test cases.

For each test case, there is only one line describing the given string $s (1\leq |s| \leq 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

2
bb
bab

Case #1: 27
Case #2: 651

Hint

For the first sample, the representative strings smaller than or equal to bb are aa, ab, …, az, bb.