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

Hint

wange2014

Source

2015 ACM/ICPC Asia Regional Shenyang Online

提交代码