题目描述
小张得到了一个序列f,这个序列f不递减,且f[1]等于f[2].
f[1]等于最小的质数减1;这个序列f的满足以下要求
1.每3个连续的数中有且只有一个被2整除.
2.每4个连续的数中有且只有一个被3整除.
3.每5个连续的数中有且只有一个被5整除.
4.每6个连续的数中有且只有一个被8整除.
5.每7个连续的数中有且只有一个被13整除.
6.每8个连续的数中有且只有一个被21整除.
7.每9个连续的数中有且只有一个被34整除.
....依此类推
一共T组样例
他想知道从f[1]的平方到f[x]的平方和是多少,以及序列f[1]到f[2*x]的奇数项之和,结果对1e9+7取模。
输入描述
第一行输入T,接下来T行每行输入x.
输出描述
每行输出两个第一个平方和,第二个序列的奇数项之和,结果对1e9+7取模.
样例输入
4 5 4 25 1000000
样例输出
40 55 15 21 107509762 586268941 810509319 815776844
数据范围
$T <= 10^6,0 < x <= 10^6$
