题目描述

原题来自 SPOJ - LCMSUM

给定 $n$，计算下式的值：

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

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

输入格式

第一行包含一个整数 $T$，表示数据组数；

接下来 $T$ 行，每行一个整数 $n$。

输出格式

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

样例

input

3
1
2
5

output

1
4
55

数据范围与提示

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