Friendship of Frog

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 65536/65536 K (Java/Others)

Description

$N$ frogs from different countries are standing in a line. Each country is represented by a lowercase letter. The distance between adjacent frogs (e.g. the $1^{st}$ and the $2^{nd}$ frog, the $N - 1^{th}$ and the $N^{th}$ frog, etc) are exactly $1$. Two frogs are friends if they come from the same country.

The closest friends are a pair of friends with the minimum distance. Help us find that distance.

Input

First line contains an integer $T$, which indicates the number of test cases.

Every test case only contains a string with length $N$, and the $i^{th}$ character of the string indicates the country of $i^{th}$ frogs.

$\cdot$ $1 \leq T \leq 50$.

$\cdot$ for 80% data, $1 \leq N \leq 100$.

$\cdot$ for 100% data, $1 \leq N \leq 1000$.

$\cdot$ the string only contains lowercase letters.

Output

For every test case, you should output "Case #x: y", where $x$ indicates the case number and counts from $1$ and $y$ is the result. If there are no frogs in same country, output $-1$ instead.

Sample Input

2 abcecba abc

Sample Output

Case #1: 2 Case #2: -1

Hint

wange2014

Source

2015ACM/ICPC亚洲区上海站-重现赛(感谢华东理工)

提交代码