Jesus Is Here

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.

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.

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.

9
5
6
7
8
113
1205
199312
199401
201314

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

2015 ACM/ICPC Asia Regional Shenyang Online