Jesus Is Here

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

Memory Limit: 65535/102400 K (Java/Others)

Description

I've sent Fang Fang around 201314 text messages in almost 5 years. Why can't she make sense of what I mean?
But Jesus is here!" the priest intoned. Show me your messages."
Fine, the first message is $s_1=\texttt{c}"$ and the second one is $s_2=\texttt{ff}"$.
The $i$-th message is $s_i = s_{i-2} + s_{i-1}$ afterwards. Let me give you some examples.
$s_3 = \texttt{cff}"$, $s_4 = \texttt{ffcff}"$ and $s_5 = \texttt{cffffcff}"$.

I found the $i$-th message's utterly charming," Jesus said.
Look at the fifth message". $s_5 = \texttt{cffffcff}"$ and two $\texttt{cff}"$ appear in it.
The distance between the first $\texttt{cff}"$ and the second one we said, is $5$.
You are right, my friend," Jesus said. Love is patient, love is kind.
It does not envy, it does not boast, it is not proud. It does not dishonor others, it is not self-seeking, it is not easily angered, it keeps no record of wrongs.
Love does not delight in evil but rejoices with the truth.
It always protects, always trusts, always hopes, always perseveres."

Listen - look at him in the eye. I will find you, and count the sum of distance between each two different $\texttt{cff}"$ as substrings of the message.

Input

An integer $T~(1\le T\le 100)$, indicating there are $T$ test cases.
Following $T$ lines, each line contain an integer $n~(3\le n\le 201314)$, as the identifier of message.

Output

The output contains exactly $T$ lines.
Each line contains an integer equaling to:
$$\sum_{i<j:s_n[i..i+2]=s_n[j..j+2]=\texttt{cff}"}(j-i)~mod~530600414,$$
where $s_n$ as a string corresponding to the $n$-th message.

Sample Input

9
5
6
7
8
113
1205
199312
199401
201314

Sample Output

Case #1: 5
Case #2: 16
Case #3: 88
Case #4: 352
Case #5: 318505405
Case #6: 391786781
Case #7: 133875314
Case #8: 83347132
Case #9: 16520782

wange2014

Source

2015 ACM/ICPC Asia Regional Shenyang Online