最近陶陶在研究数论，某天他偶然遇到一道题：对于给定的正整数 ，求出下面这样一个式子的值：
其中 表示正整数 和 最小公倍数，即能同时被 和 整除的最小正整数。
作为神犇的陶陶，当然轻松秒杀了这道题。不过他希望你写一个程序，用来检验他算的答案是否正确。
第一行包含一个正整数 ，表示有 组测试数据。 接下来 行，每行给出一个正整数 。
包含 行，依次表示相应答案。
7 1 10 100 1000 10000 100000 1000000
1 2127 18446224 183011304660 1827127167830060 18269345553999897648 182690854273058293758232
对于 的数据，保证 。
