#6375. LCMSUM

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

题目描述

Given n, calculate the sum LCM(1,n) + LCM(2,n) + .. + LCM(n,n), where LCM(i,n) denotes the Least Common Multiple of the integers i and n.

输入格式

The first line contains T the number of test cases. Each of the next T lines contain an integer n.

输出格式

Output T lines, one for each test case, containing the required sum.

样例

样例输入

3
1
2
5

样例输出

1
4
55

数据范围与提示

1<=T<=300000 1<=n<=1000000