wky巨佬是热爱公式的人

他综合考虑了时间复杂度（T）、空间复杂度（S）以及玄学（T*S）对算法花费的影响，定义了算法花费计算公式C=T+S/2（向下取整）+T*S( C,T,S均为大于0的整数）

  但wky很快发现了问题：存在一些特定的算法花费无法用公式来计算的情况。比如不管T和S取什么值，都无法获得C=1；同样的，不管T和S取什么值，都无法获得C=3.巨佬WKY花了1秒计算出了很多无法通过公式计算的数，他将这些无法通过算法公式计算得到的算法花费按大小排列成一个数列a[]，你能知道它的第n位吗

第一行一个数t表示询问个数

之后t行每行一个数n表示求出数列第n位%(1e9+7)的值；

输出 共t行，每行一个数表示a[n]%(1e9+7)的值

1<=t<=100000,1<=n<=10;