题目描述

我们有一个序列，现在它里面有三个数$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$。

评测数据说明

本题使用按题意独立构造、以独立程序核对的训练数据及公开样例，共10个测试点，非原站或官方原始数据。总分100分。