题目描述

给定 $n$，求

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

输入格式

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

输入的第一行是一个整数 $T$，表示数据组数。

接下来 $T$ 行，每行一个整数，表示一组数据的 $n$。

输出格式

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

3
1
2
5

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$。