疯狂 LCM

题目背景

众所周知,czmppppp 是数学大神犇。一天,他给众蒟蒻们出了一道数论题,蒟蒻们都惊呆了。

题目描述

给定 $n$,求 $$\sum_{i = 1}^n \operatorname{lcm}(i, n)$$ 其中 $\operatorname{lcm}(i, j)$ 表示 $i$ 和 $j$ 的最小公倍数。

输入输出格式

输入格式


**本题单测试点内有多组数据**。 输入的第一行是一个整数 $T$,表示数据组数。 接下来 $T$ 行,每行一个整数,表示一组数据的 $n$。

输出格式


对于每组数据,输出一行一个整数表示答案。

输入输出样例

输入样例 #1

3
1
2
5

输出样例 #1

1
4
55

说明

#### 数据规模与约定 - 对于 $30\%$ 的数据,保证 $T \leq 5$,$n \leq 10^5$。 - 对于 $100\%$ 的数据,$1 \leq T \leq 3 \times 10^5$,$1 \leq n \leq 10^6$。