序列

【题目描述】

我们有一个序列，现在它里面有三个数$1,2,2$。我们从第三个数开始考虑： 1、第三个数是$2$，所以我们在序列后面写$2$个$3$，变成$1,2,2,3,3$。 2、第四个数是$3$，所以我们在序列后面写$3$个$4$，变成$1,2,2,3,3,4,4,4$。 那么你可以看到，这个序列应该是$1,2,2,3,3,4,4,4,5,5,5,6,6,6,6,…$。 如果我们设一个数N最后出现的位置为$last(N)$，那么现在我希望知道$last(N)$等于多少。

【输入】

第一行一个整数$T$，代表数据组数。 接下来$T$行每行一个整数$N$。

【输出】

$T$行，每行一个整数，代表$last(last(N))\bmod (10^9+7)$的值。

【输入样例】

3
3
10
100000

【输出样例】

11
217
507231491

【提示】

【数据规模】 对于30%的数据，$1≤N≤10^3$。 对于60%的数据，$1≤N≤10^6$。 对于100%的数据，$1≤N≤10^9,1≤T≤2×10^3$。