题目描述

小P 最近在数论课上接触到了「因子」这个概念，于是他突发奇想，定义了下面这个函数。

对于一个整数 $n$，如果整数 $d$ 满足 $d \mid n$ 且 $\gcd\left(d, \dfrac{n}{d}\right) = 1$，那么就称 $d$ 是 $n$ 的一个「小P 因子」。

定义函数 $ddl^*(n)$ 表示 $n$ 的所有小P 因子之和，即

$$ddl^*(n) = \sum_{\substack{d \mid n \\ \gcd\left(d,\, n/d\right) = 1}} d$$

例如：

• $ddl^*(1) = 1$；
• $ddl^*(2) = 1 + 2 = 3$；
• $ddl^*(6) = 1 + 2 + 3 + 6 = 12$。

现在给定 $T$ 次询问，每次给出一个整数 $n$，请你求出

$$F(n) = \sum_{i=1}^{n} ddl^*(i)$$

输入格式

第一行一个整数 $T$，表示询问次数。

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

输出格式

输出 $T$ 行，每行一个整数，依次表示每个询问的答案。

输入输出样例 #1

输入 #1

1
5

输出 #1

19

输入输出样例 #2

输入 #2

1
100

输出 #2

6889

输入输出样例 #3

输入 #3

1
100000

输出 #3

6842185909

说明

样例解释

$ddl^*(1)$ 到 $ddl^*(5)$ 依次为 $1, 3, 4, 5, 6$，所以 $F(5) = 1+3+4+5+6 = 19$。

数据范围

• 对于 $30\%$ 的数据，$T \le 10$，$n \le 10^5$。
• 对于 $60\%$ 的数据，$T \le 10$，$n \le 10^7$。
• 对于 $100\%$ 的数据，$1 \le T \le 10$，$1 \le n \le 10^{10}$。