题干：

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 s1=‘‘c"s1=‘‘c" and the second one is s2=‘‘ff"s2=‘‘ff". 
The ii-th message is si=si−2+si−1si=si−2+si−1 afterwards. Let me give you some examples. 
s3=‘‘cff"s3=‘‘cff", s4=‘‘ffcff"s4=‘‘ffcff" and s5=‘‘cffffcff"s5=‘‘cffffcff". 

``I found the ii-th message's utterly charming," Jesus said. 
``Look at the fifth message". s5=‘‘cffffcff"s5=‘‘cffffcff" and two ‘‘cff"‘‘cff" appear in it. 
The distance between the first ‘‘cff"‘‘cff" and the second one we said, is 55. 
``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 ‘‘cff"‘‘cff" as substrings of the message. 

Input

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

Output

The output contains exactly TT lines. 
Each line contains an integer equaling to: 

∑i<j:sn[i..i+2]=sn[j..j+2]=‘‘cff"(j−i) mod 530600414,∑i<j:sn[i..i+2]=sn[j..j+2]=‘‘cff"(j−i) mod 530600414,


where snsn as a string corresponding to the nn-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

题目大意：

   字符串s[1]="c",s[2]="ff",s[i]=s[i-2]+s[i-1](i>=3);

   对于每个n,求s[n]中所有的任意两个字符c的距离之和f[n]；

解题报告：

   同时维护五个值然后dp就行了。对于f[i]，为f[i-1]+f[i-2]左右两侧分别的 + 左侧对右侧造成的贡献。所以求f[i]的同时维护一下每个字符串的  所有c到右侧的距离和  ，  所有c到左侧的距离和，c的个数，字符串长度。

AC代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define F first
#define S second
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
typedef pair<int,int> PII;
const int MAX = 3e5 + 5;
const ll mod = 530600414LL;
ll l[MAX],r[MAX],f[MAX],len[MAX],c[MAX];
int main()
{
	len[3] = 3;
	len[4] = 5;
	l[4] = 3;
	r[4] = 3;
	c[4] = 1;
	l[5] = 1 + 6;
	r[5] = 3 + 8;
	c[5] = 2;
	len[5] = len[4] + len[3];//8
	l[6] = 3 + 6 + 11;//l[4] + len[4]*c[5] + l[5]
	r[6] = 3 + 8 + 11;//r[5] + c[4]*len[5] + r[4]
	c[6] = c[5]+c[4];
	len[6] = len[5]+len[4];
	f[5] = 5;f[6] = 16;
	for(int i = 7; i<=201314; i++) {
		len[i] = len[i-1] + len[i-2];
		c[i] = c[i-1]+c[i-2];
		l[i] = l[i-2] + len[i-2]*c[i-1] + l[i-1];
		r[i] = r[i-1] + c[i-2]*len[i-1] + r[i-2];
		f[i] = f[i-1]+f[i-2] + (r[i-2]-c[i-2]+mod)*(c[i-1]) + c[i-2]*(l[i-1]);
		l[i]%=mod;r[i]%=mod;
		f[i]%=mod;
		len[i]%=mod;
		c[i]%=mod;
	}
	int t,n,iCase=0;
	cin>>t;
	while(t--) {
		scanf("%d",&n);
		printf("Case #%d: %lld\n",++iCase,f[n]%mod);
	}
	return 0 ;
}