你的生日快到了！你预订了一个 $n$ 克的蛋糕，并准备在生日派对上与朋友们分享。

你想邀请 $m$（$0 \le m < n$）个朋友来参加。这样派对上总共会有 $m + 1$ 个人。唱完生日歌并许愿后，就到了吃美味蛋糕的时间了！由于某些原因，每个人分到的蛋糕大小必须是相同的整数 $k$，且 $k$ 必须尽可能大。改变来参加的朋友人数，整数 $k$ 也可能会随之改变。记 $S_n$ 为通过控制朋友人数所能得到的、所有不同的 $k$ 组成的集合。

计算单个 $S_n$ 的大小太简单了。因此，你需要计算 $\sum_{i=1}^n |S_i|$，其中 $|S|$ 表示集合 $S$ 的大小。

输入格式

输入的第一行包含一个整数 $T$（$T \le 10^5$），表示测试用例的数量。

接下来的第 $2$ 到第 $T + 1$ 行，每行包含一个整数 $n$（$1 \le n \le 10^9$），表示一次查询。

输出格式

对于每个测试用例，输出一行，包含一个整数，表示该测试用例的答案。由于答案可能很大，你只需要输出其模 $10^9 + 7$ 的值。

样例

输入样例 1

6
1
1
4
5
1
4

输出样例 1

1
1
8
11
1
8