# LCMSUM - LCM Sum

## 题意翻译

- $T$ 次询问，每次询问给定 $n$，求 $$\sum_{i=1}^n\operatorname{lcm}(i,n)$$ - $1\le T\le 3\times 10^5$，$1\le n\le 10^6$。

## 题目描述

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.

## 输入输出样例

### 输入样例 #1

3
1
2
5

### 输出样例 #1

1
4
55