#6375. LCMSUM

内存限制:256 MiB 时间限制:500 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

原题来自 SPOJ - LCMSUM

给定 n ,计算下式的值:

\sum_{i=1}^n\text{lcm}(i,n)

其中 \text{lcm}(i,n) 表示 i,n 的最小公倍数。

输入格式

第一行包含一个整数 T ,表示数据组数;

接下来 T 行,每行一个整数 n

输出格式

输出 T 行,每行一个整数,表示这组数据的答案。

样例

样例输入

3
1
2
5

样例输出

1
4
55

数据范围与提示

对于所有数据, 1\le T\le 3\times 10^5,1\le n\le 10^6