#P1891. 疯狂 LCM

疯狂 LCM

题目背景

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

题目描述

给定 nn,求

i=1nlcm(i,n)\sum_{i = 1}^n \operatorname{lcm}(i, n)

其中 lcm(i,j)\operatorname{lcm}(i, j) 表示 iijj 的最小公倍数。

输入格式

本题单测试点内有多组数据

输入的第一行是一个整数 TT,表示数据组数。

接下来 TT 行,每行一个整数,表示一组数据的 nn

输出格式

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

3
1
2
5
1
4
55

提示

数据规模与约定

  • 对于 30%30\% 的数据,保证 T5T \leq 5n105n \leq 10^5
  • 对于 100%100\% 的数据,1T3×1051 \leq T \leq 3 \times 10^51n1061 \leq n \leq 10^6