Problem J: 看似简单的题目

"
Time Limit $1$ 秒/Second(s) Memory Limit $512$ 兆字节/Megabyte(s)
提交总数 $29$ 正确数量 $11$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签 数论 数学
众所周知,欧拉函数$\phi(n)$表示小于或等于$n$ 的正整数中与$n$互质的数的个数。现在定义$f(n)$如下: $$f(n)=(\sum_{i=1}^{n}\phi(n^i))\mod(n+1)$$ 如果要是让你求$f(n)$,那非常简单,现在需要求的是它的前缀和$g(n)$。$g(n)$的定义如下: $$g(n)=\sum_{i=1}^{n}f(i)$$ 当然这仍然是非常简单的,你可以告诉我是多少吗?
第一行输入正整数$T$,表示数据的组数。 每组数据为一个正整数n。 数据范围: $1 \le n$,$T \le 10^6$ 。
对于每组数据,输出一行,格式为'Case #t: x',t 为数据的组 号,$x$ 为$g(n)$的值。
3
10
10000
3
Case 1: 19
Case 2: 20263333
Case 3: 3