有n个界徐盛,编号为1到n,第i个界徐盛的编号为i,每个界徐盛都需要一些酒,一缸酒需要一块钱,同时,编号为i的界徐盛认为他获得的酒的数量不能为i的因子，不然他就会生气并装备古锭刀火杀你,求使得所有界徐盛获得满足要求的酒的数量时的最小花费

输入

多组测试数据。

第一行：一个数t,表示测试数据组数

之后t行，每行一个数n,表示界徐盛的数量

输出

输出t行，每行一个数,对应 最小的花费，答案对1e9+7 取模。

输入样例

5

1

2

3

4

10

输出样例

2

5

7

10

26

数据非常大，n会到10^16，t会到10^5