#pragma warning(disable:4996)

#include <cstdio>
#include <string.h>

#include <vector>
using namespace std;

//#define max(a,b) (a>b?a:b)
const int MOD = 1000000007;
int cache[7][1000];
//남은 영역 w에 대해 경우의 수를 계산하는 함수 

/*
Type 에 따라서 다은 처리할 수 있는 타입이 결정된다. 
    1       2       3       4       5       6
    --      --      --      i       i       --
    --      --      i       i       i        i
    --      i       i       --      i        i
    --      i       --      --      i       --

다음처리 가능 타입
    2,3,4,5       4,1          3,1           2,1             1      1,2,3,4,5
   남은 넓이에 따른 처리 수   
   (1):5             (1):0  (1):0       (1):0       (1):5           (1) : 5
   (2):1,2,3,4,5   (2):1,4    (2):1,6   (2):1,2 (2):1,2,3,4,5   (2) : 1,2,3,4,5

    3일 경우 처리 될 수 있는 타입
    --      --        --    
    ii      i--       i
    ii      i--          i
    --      --           --
    1       3           

    2,3,4 타입 처리시 받는 타입의 필요 잔량 넓이가 존재한다. 
*/
int n;
int width;
int depth = 0;

int titling(int w, int type)
{
    //printf( "depth = %d\n", depth ++);
    //1일 때와 0일 때 각 타입에 따른 리턴값이 다르다. 
    if(w < 0)
        return 0;

    if(w <= 1)
    {       
        if(w == 1) // 어떤 타입이던 1줄이 남은 경우 는 완료 한것으로 판단한다. 
        {
        //  printf( "depth = %d\n", --depth);
            return 1; 
        }

        if(w == 0 && (type == 1 || type == 5)) //남은 넓이가 없다면 type 2,3,4 는 처리할 수 없다. 
        {
        //  printf( "depth = %d\n", --depth);
            return 1; 
        }

        if(type == 1 || type ==5)
            printf("add condition\n");

        //printf( "depth = %d\n", --depth);
        return 0;       
    }

    int & ret = cache[type][w]; //해당 타입에서 넓이가 남았을 경우 경우의 수 메모이제이션 값 
    if(ret != -1)
    {
    //  printf( "depth = %d\n", --depth);
        return ret; 
    }

    switch(type)
    {       
    case 1:
    case 5: 
    case 6:
        ret =  (titling(w-2, 1) + titling(w-1,2) + titling(w-1,3) + titling(w-1,4) + titling(w-1,5))%MOD;       
        break;
    case 2:             
        ret = (titling(w-1,5) + titling(w-1, 4))%MOD;       
        break;
    case 3:
        if(w == 2)
            ret = 1; // 남은 넓이가 2이고 타입이 3이면 항상 1이된다. 
        else
            ret = (titling(w-1,5) + titling(w-2, 3))%MOD;  //3타입에서 3타입으로 갈 때는 2개의 w 이 줄게 된다.        
            //** 이부분을 새로운 타입 6을 만들어 처리해야 할 수 있다. ㄷ 형과 역ㄷ 에 따른 한번은 -2 한번은 -1 로 처리되어야 한다. 
            //  하지만 그렇게 되면 w-1, 5 와 w-2 6에서 중복되는 부분이 생기는가? 생긴다. 즉 
            /*
                --i
                iii
                iii
                --i
                 처럼되어 다시 계산하는 것과 
                ----
                i--i
                i--i
                ----
                이것 은 같은 시작 모양을 만들지만 남은 w가 다르게 된다.  이것을 어떻게 처리해야 하는가?
            */
        break;
    case 4:     
        ret = (titling(w-1,5) + titling(w-1, 2))%MOD;       
        break;
    }

    return ret;
}

int main()
{
    int T;

    //freopen("D:\\MyProject\\CodeJam\\연습\\SampleCode\\a.in", "r", stdin);
    scanf("%d", &T);
    int j = 1;
    while(T--)
    {           
        scanf("%d",&width);

        for(int i1 =0; i1 < 7; i1++)
            for(int i=0; i<1000;i++)
                cache[i1][i] = -1;

        printf("%d %d\n",j++, titling(width, 1));       
    }
    return 0;
}