2401 - 陶陶的难题I

最近陶陶在研究数论，某天他偶然遇到一道题：对于给定的正整数???，求出 下面这样一个式子的值：

其中LCM(a???, b???)表示正整数???和???最小公倍数，即能同时被a???和b???整除的最小正 整数。 作为神犇的陶陶，当然轻松秒杀了这道题。不过他希望你写一个程序，用来 检验他算的答案是否正确。

第一行包含一个正整数???T，表示有T???组测试数据。接下来???T<=10^5 行，每行给出一个正整数N,N<=10^6。

包含T???行，依次给出对应的答案。