#include <bits/stdc++.h>
using namespace std;
long long MAXN=1000000;
long long dp[1000000+1];
int main() {
// your code goes here
ios::sync_with_stdio(false);
cin. tie(NULL);
cout. tie(NULL);
long long k=1000000007;
dp[0]=dp[1]=0;
dp[2]=dp[3]=1;
for(int i=4;i<=MAXN;i++)
{
dp[i]=(dp[i-2]%k+dp[i-3]%k)% k;
}
int t; cin>>t;
while(t--){
long long N; cin>>N;
cout<<dp[N]<<"\n";
}
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7Cgpsb25nIGxvbmcgTUFYTj0xMDAwMDAwOwpsb25nIGxvbmcgZHBbMTAwMDAwMCsxXTsKCmludCBtYWluKCkgewoJLy8geW91ciBjb2RlIGdvZXMgaGVyZQoJaW9zOjpzeW5jX3dpdGhfc3RkaW8oZmFsc2UpOwogICAgY2luLiB0aWUoTlVMTCk7CiAgICBjb3V0LiB0aWUoTlVMTCk7CiAgICBsb25nIGxvbmcgaz0xMDAwMDAwMDA3OwogICAgZHBbMF09ZHBbMV09MDsKCWRwWzJdPWRwWzNdPTE7Cglmb3IoaW50IGk9NDtpPD1NQVhOO2krKykKCXsKCQlkcFtpXT0oZHBbaS0yXSVrK2RwW2ktM10layklIGs7Cgl9CglpbnQgdDsgY2luPj50OwoJd2hpbGUodC0tKXsKCQlsb25nIGxvbmcgIE47IGNpbj4+TjsKCQljb3V0PDxkcFtOXTw8IlxuIjsKCX0KCXJldHVybiAwOwp9