use std::io::{self, Read, Write};

fn main() {
/*
    let mut s = String::new();
    io::stdin().read_line(&mut s).unwrap();
    let n: usize = s.trim().parse().unwrap();

    let mut nums: Vec<i64> = Vec::new();
    let mut max: i64 = 0;

    for _ in 0..n {
        let mut x = String::new();
        io::stdin().read_line(&mut x).unwrap();
        let a: i64 = x.trim().parse().unwrap();
        nums.push(a);
        if a > max {
            max = a;
}*/
//  //输入太慢了过不了
    let mut buf = String::new();
    io::stdin().read_to_string(&mut buf).unwrap();
    let mut it = buf.split_whitespace();

    let m: usize = it.next().unwrap().parse().unwrap();
    let mut vec: Vec<i64> = Vec::with_capacity(m);
    let mut max: i64 = 0;

    for _ in 0..m {
        let a: i64 = it.next().unwrap().parse().unwrap();
        vec.push(a);
        if a > max { max = a; }
    }

    let mut dp: Vec<i64> = vec![0; (max + 1) as usize];
    if max >= 0 { dp[0] = 1; }
    if max >= 1 { dp[1] = 1; }
    if max >= 2 { dp[2] = 2; }
    if max >= 3 { dp[3] = 4; }

    for i in 4..=max {
        dp[i as usize] = dp[(i - 1) as usize] + dp[(i - 2) as usize] + dp[(i - 3) as usize] + dp[(i - 4) as usize];
    }

    let mut out = String::new();
    for i in vec {
        out.push_str(&format!("{}\n", dp[i as usize]));
    }
    io::stdout().write_all(out.as_bytes()).unwrap();
}