#include <cstdio>

 #include <cstring>

 #include <string>

 #include <algorithm>

 using namespace std;

 #define MOD 1000000007

 #define LL __int64

 LL dp[];

 int que[],flag[];

 int main()

 {

     int i,n,t,j,num;

     LL x;

     num = ;

     for(i = ;;i ++)

     {

         t = (*i*i - i)/;

         if(t > ) break;

         flag[num] = i;

         que[num++] = t;

         t = (*i*i + i)/;

         flag[num] = i;

         que[num++] = t;

     }

     dp[] = ;dp[] = ;

     dp[] = ;

     for(i = ;i <= ;i ++)

     {

         for(j = ;j <= ;j ++)

         {

             if(que[j] > i)

             break;

             else

             x = dp[i-que[j]];

             if(flag[j]% == )

             {

                 dp[i] = (dp[i] + x)%MOD;

             }

             else

             {

                 dp[i] = (dp[i] - x)%MOD;

                 if(dp[i] < )

                 dp[i] += MOD;

             }

         }

     }

     scanf("%d",&t);

     while(t--)

     {

         scanf("%d",&n);

         printf("%I64d\n",dp[n]);

     }

     return ;

 }