无额外样例。

题目描述

给出一个整数 $n$，求：

其中 $lcm(i,n)$ 表示整数 $i$ 和 $n$ 的最小公倍数。

多组数据。

输入

第一行：一个整数 $T$，表示数据组数。

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

输出

共 $T$ 行，每组数据的答案占一行。

样例输入

7
1
10
100
1000
10000
100000
1000000

样例输出

1
320
286600
279952000
278320460000
277913417200000
277811686426000000

数据范围

$1 ≤ T ≤ 3 × 10^5, 1 ≤ n ≤ 10^6$