firstdata = int(input());
result = 0;
siteik = 0;

for inp in range(0,firstdata):
    first = 0;
    second = 0;
    third = 0;
    four = 1;
    siteik = int(input());
    if siteik < 4:
        print(0);
    elif siteik == 4:
        print(1);
    else:
        for inp2 in range(5,siteik+1):
            result = (first+second+third+four)%17;
            first = second;
            second = third;
            third = four;
            four = result;
        print(result);