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

你想邀请 $m$（$0 \le m < n$）个朋友来参加。这样派对上总共有 $m + 1$ 个人。唱完生日歌并许愿后，就到了吃美味蛋糕的时间了！由于某些原因，每个人的蛋糕大小必须是相同的整数 $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