var n, array = [], m,array2 = [];n = read_line();n = parseInt(n);    while(m = read_line()){  array.push(parseInt(m));    }for(var i = 0; i < n; i++){    array2[i] = func(array[i]);}for(var x = 0; x < array2.length; x++){print(array2[x]);}function func(m){    if(m >= 4){        return func(m - 1) + func(m - 2);    }else if(m == 3){        return 2;    }else if(m == 2){        return 1;    }else if(m == 1){        return 0;    }}