[AdditionalFile6375.zip](file://AdditionalFile6375.zip?type=additional_file)

#6375. LCMSUM

标签: 传统 | 时间限制: 500 ms | 内存限制: 256 MiB |

题目描述

原题来自 SPOJ - LCMSUM

给定 $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$。