Coding is the closest thing we have to a surperpower
描述
定义函数 \varphi(x) 为 1 到 x-1 与 x 互质的个数。
现在给定一段区间 [l,r]，要求计算下列式子:
\sum_{i=l}^r\varphi(i)^2
输入
输入以整数 T(1≤T≤10^5)开始，表示测试用例的数量。
每个测试用例将包含整数 l,r (2 ≤ l ≤ r ≤ 5 * 10^{6})。
输出
共有 T 行。对于每组测试数据，输出一行信息 "Case t: A" （不含引号）。
其中 t 表示对应的是第几组测试数据，A 表示对应的答案。
样例
输入
3 6 6 8 8 2 20
输出
Case 1: 4 Case 2: 16 Case 3: 1237
标签