题目描述

对于给定的整数$n$，对于全部的二元组$(i,j)$满足$1\le i<j\le n$，计算$\frac{i+j}{gcd(i,j)}$之和。由于答案可能很大，请将答案对$10^9+7$取模后输出。

$gcd$，即最大公因数，指两个整数共有约数中最大的一个。例如，$12$和 $30$的公约数有$1,2,3,6$，其中最大的约数是$6$，因此$gcd(12,30) =6$。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数$T(1\le T\le 10^5)$代表数据组数，每组测试数据描述如下:

在一行上输入一个整数$n(1\le n\le 10^6)$代表给定的整数。

除此之外，保证$\sum n \le 10^9$

输出描述

对于每组测试用例如果无解，请输出$-1$。

否则输出$n$个正整数$a_i$，代表麻薯哥构造的排列。有多解时输出任意合法解。

样例

输入

4
2
3
10
114514

输出

3
12
396
853391453

样例解释

对于第二组测试数据，满足条件的二元组为$(1,2),(1,3),(2,3)$。他们对应的值分别为$\frac{1+2}{1}=3,\frac{1+3}{1}=4,\frac{2+3}{1}=5$，所以答案为$3+4+5=12$。